LeetCode-236. Lowest Common Ancestor of a Binary Tree

发表于 分类于

问题描述

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:

img

1
2
3
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Constraints:

  • The number of nodes in the tree is in the range [2, 105].
  • -109 <= Node.val <= 109
  • All Node.val are unique.
  • p != q
  • p and q will exist in the tree.

解答

方法一：DFS递归遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/*
 * @Description: 236. Lowest Common Ancestor of a Binary Tree
 * @Author: libk
 * @Github: https://github.com/libk
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @description: DFS递归
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
const lowestCommonAncestor = function (root, p, q) {
  if (root === null || p === root || q === root) {
    return root // 只要当前根节点是p和q中的任意一个，就返回根节点
  }

  // 根节点不是p和q中的任意一个，那么就继续分别往左子树和右子树找p和q
  let left = lowestCommonAncestor(root.left, p, q)
  let right = lowestCommonAncestor(root.right, p, q)

  // 左子树和右子树都没有找到，返回null
  if (left === null && right === null) {
    return null
  } else if (left === null) { // 左子树没有p也没有q，就返回右子树的结果
    return right
  } else if (right === null) { // 右子树没有p也没有q，就返回左子树的结果
    return left
  } else {
    return root // 左右子树都找到p和q了，那就说明p和q分别在左右两个子树上，所以此时的最近公共祖先就是root
  }
}
方法二：DFS过程中在哈希表中存储每个节点的父节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/*
 * @Description: 236. Lowest Common Ancestor of a Binary Tree
 * @Author: libk
 * @Github: https://github.com/libk
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @description: DFS过程中在哈希表中存储每个节点的父节点
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
const lowestCommonAncestor = function (root, p, q) {
  const parentNodes = {}
  const visited = []

  const dfs = (cur) => {
    if (cur.left) {
      parentNodes[cur.left.val] = cur
      dfs(cur.left)
    }
    if (cur.right) {
      parentNodes[cur.right.val] = cur
      dfs(cur.right)
    }
  }

  dfs(root)

  while (p) {
    visited.push(p.val)
    p = parentNodes[p.val]
  }

  while (q) {
    if (visited.includes(q.val)) {
      return q
    }
    q = parentNodes[q.val]
  }
  
  return null
}