题目描述

[EN | CN]

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

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个结点也可以是它自己的祖先)。”

例如,给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

1
2
3
4
5
6
7
3
   /   \
  5     1
 / \   / \
6   2 0   8
   / \
  7   4

示例 1:

1
2
3
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 结点 5 和结点 1 的最近公共祖先是结点 3。

示例 2:

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

说明:

  • 所有结点的值都是唯一的。
  • p、q 为不同结点且均存在于给定的二叉树中。

解法 1:先找路径再合并

分别找到从根结点到 p、从根结点到 q 的路径,然后二路归并,找到最深的共同祖先结点。

这个做法比较直接,不过效率不太好,因为是分开找 pq 的,最坏情况下需要遍历两遍所有结点。

复杂度分析略。

实现与结果略。

解法 2:递归

我们尝试分析 pq 可能出现的情况:

  • 如果 pq 都在左子树,那么返回 LCA(root.left)
  • 如果 pq 都在右子树,那么返回 LCA(root.right)
  • 如果 pq 分别在左右子树,那么返回 root
  • 如果 pq 一个在 root,一个在子树,那么返回 root

那么我们可以分别对 root 的左右子树分别调用 LCA

  • 如果 LCA(root.left)LCA(root.right) 分别找到了 pq 中的一个,那么返回 root
  • 如果只有 LCA(root.left) 找到了 pq 中的一个,那么返回找到的这个结点(另一个结点必然在它之下);
  • 如果只有 LCA(root.right) 找到了 pq 中的一个,那么返回找到的这个结点。

而在 LCA 的实现内部,其实我们没必要 pq 都找到,只需要找到一个就返回即可,因为配合另一棵子树就可以推断出他们的最深共同祖先结点了。

复杂度分析略。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root in [None, p, q]:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if not left:
            return right
        if not right:
            return left
        return root
  • 执行用时:92 ms,在所有 Python3 提交中击败了 54.86% 的用户。
  • 内存消耗:23.9 MB,在所有 Python3 提交中击败了 33.33% 的用户。