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

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

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

解题思路

首先在解这道题之前我们必须得理解什么是最近的公共祖先。

用图来解释比较好理解，有以下几种情况：

1. 节点p、q中，其中一个为另外一个的子节点

   

2. 如果节点p、q为某一个节点root的左右子树，那么它们的最近公共祖先就是root

   

3. 如果root的左右子树中都不包含p、q，返回null

根据这三种情况我们可以得到递归的基本条件

1. 终止条件

   如果root为空，返回null（说明在该节点下并未找到p或者q）

   如果root等于p或者q，返回root(说明在该节点下找到了p或者q)

   if not root or root == p or root == q: return root
   

   2.递归

   • 递归左右子节点，各标记为left，right

   left = self.lowestCommonAncestor(root.left, p, q)
   right = self.lowestCommonAncestor(root.right, p , q) 
   

2. 返回值,可以分为三种情况:

   • left和right都为空，返回null
   • left或者right其中一个为空，返回不为空的一个
   • left和right都不为空，说明p、q分别在root的左右两侧，那么root就是他们的公共祖先，返回root

if not left: return right
if not right: return left
return root

最终代码:

# 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 not root or root == p or root == 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

复杂度分析

时间复杂度: O(N)

空间复杂度: O(N)