LeetCode-236.二叉树的最近公共祖先

发表于 分类于

题目描述

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例

给定二叉树：

1
root = [3,5,1,6,2,0,8,null,null,7,4]
1
2
3
输入：p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
1
2
3
输入：p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

提示：

  • 树中节点数目在范围 [2, 105]内。
  • -109 <= Node.val <= 109
  • 所有Node.val互不相同 。
  • p != q
  • p和q均存在于给定的二叉树中。

题解

方法1：递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? {
  // 只要当前根节点是p和q中的任意一个，就返回根节点
  if root === nil || p === root || q === root {
    return root
  }
  
  // 根节点不是p和q中的任意一个，那么就继续分别往左子树和右子树找p和q
  let left = lowestCommonAncestor(root?.left, p, q)
  let right = lowestCommonAncestor(root?.right, p, q)
  
  // 左子树和右子树都没有找到，返回null
  if left === nil && right === nil {
    return nil
  }
  if left === nil { // 左子树没有p也没有q，就返回右子树的结果
    return right
  }
  if right === nil { // 右子树没有p也没有q，就返回左子树的结果
    return left
  }
  // 左右子树都找到p和q了，那就说明p和q分别在左右两个子树上，所以此时的最近公共祖先就是root
  return root
}

方法2：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
func lowestCommonAncestor2(_ root: TreeNode?, _ p: TreeNode?, _ q: TreeNode?) -> TreeNode? {
  // 所有节点值对应的父节点
  var allSuperNodes = [Int: TreeNode]()
  // p节点的所有父节点的值
  var pSuperValues = [Int]()

  func dfs(_ cur: TreeNode?) {
    if let left = cur?.left {
      allSuperNodes[left.val] = cur!
      dfs(left)
    }
    if let right = cur?.right {
      allSuperNodes[right.val] = cur!
      dfs(right)
    }
  }
  // 找到每个节点值对应的父节点
  dfs(root)
  
  // 找到p节点所有的父节点值
  var pNode = p
  while pNode !== nil {
    pSuperValues.append(pNode!.val)
    pNode = allSuperNodes[pNode!.val]
  }
  
  // 顺着q节点往q的所有父节点上遍历，直到找到p的父节点中存在的节点
  var qNode = q
  while qNode !== nil {
    if pSuperValues.contains(qNode!.val) {
      return qNode
    }
    qNode = allSuperNodes[qNode!.val]
  }
  return nil
}