二叉树的最近公共祖先-python-递归
题目：
思路：
- 递归遍历：从根节点出发，递归遍历左、右子树，目标是找到
p或q； 回溯 “判断”—— 确定 LCA：递归遍历完左右子树后，会得到两个结果（
left：左子树找到的节点；right：右子树找到的节点），通过这两个结果判断当前节点的角色
| 左右子树结果 | 含义（p/q的位置） | 当前节点的角色 | 返回值 |
|---|---|---|---|
left=None + right=None | 既不在左子树，也不在右子树 | 无目标，无贡献 | None |
left=None + right≠None | 都在右子树（右子树已找到目标 / LCA） | 传递右子树的结果 | right |
left≠None + right=None | 都在左子树（左子树已找到目标 / LCA） | 传递左子树的结果 | left |
left≠None + right≠None | 分别在左、右子树（跨子树） | 自身就是最近公共祖先 | 当前节点root |
3.最终回溯 —— 定位最深 LCA
递归会从叶子节点向上回溯，每一层都按上述规则判断：
- 若
p/q都在某一子树中，结果会持续向上传递该子树的 LCA； - 若
p/q分属左右子树，当前节点就是 “最深” 的公共祖先（因为再往下的子树只能找到其中一个目标）。
代码：
# 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': //只要当前根节点是p和q中的任意一个，就返回（因为不能比这个更深了，再深p和q中的一个就没了） if not root or root == p or root == q: return root //根节点不是p和q中的任意一个，那么就继续分别往左子树和右子树找p和q left = self.lowestCommonAncestor(root.left,p,q) right = self.lowestCommonAncestor(root.right,p,q) //p和q都没找到，那就没有 if not left and not right: return None //左子树没有p也没有q，就返回右子树的结果 if not left: return right //右子树没有p也没有q就返回左子树的结果 if not right: return left //左右子树都找到p和q了，那就说明p和q分别在左右两个子树上，所以此时的最近公共祖先就是root return root