LeetCode(python)——236.二叉树的最近公共祖先

题目

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

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

示例 1：

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

示例 2：

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

示例 3：

输入：root = [1,2], p = 1, q = 2输出：1

提示：

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

思路

规律：p、q节点要么在分叉点（最近公共祖先就是分叉交点），要么在同一边（最近公共祖先是两者中的一个）

利用后序遍历去找左右子树，如果找到p、q则返回，如果为空（没找到p、q）返回None

用left去记录遍历左子树的结果

用right去记录遍历右子树的结果

有4种情况：
（1）left、right == null，说明都没有找到，p、q节点不在当前访问的节点的左右子树上，return None

（2）left为空，right不为空，说明p、q在右子树中，那么right就是最近公共祖先，return right（left不为空，right为空同理）

（3）left、right都不为空：说明p、q在当前访问的节点的左右子树上，当前节点就是最近公共祖先，return node

代码

# 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': return self.f(root, p ,q) # 递归函数：利用后序遍历在左右子树中找p、q def f(self, node: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': if node == None or node == p or node == q: # 如果当前节点是p、q直接返回 return node left = self.f(node.left, p, q) # 往左子树找 right = self.f(node.right, p, q) # 往右子树找 if left == None and right == None: return None # 如果都为空，说明不在当前节点下 if left and right: return node # 如果都不为空，说明分别位于当前节点的左右子树，那么当前节点就是LCA return left if left else right # 如果其中一个为空，一个不为空，说明p、q在同一边，那么不为空的left/right就是LCA