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

题目链接：236. 二叉树的最近公共祖先

题目描述

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

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

核心思考：自底向上的递归查找

寻找最近公共祖先的核心在于：判断当前节点的左、右子树中是否分别包含了目标节点 p 和 q。

1. 递归终止条件：
   • 如果当前节点 root 为空，或者 root 恰好就是 p 或 q 中的一个。这种情况下，root 本身就是我们要寻找的“线索”节点，直接返回。
2. 递归搜寻：
   • 递归进入左子树搜寻 p 和 q，记录结果为 left。
   • 递归进入右子树搜寻 p 和 q，记录结果为 right。
3. 结果判定（自顶向下回传）：
   • 双侧命中：如果 left 和 right 均不为空，说明 p 和 q 分别分布在当前节点的左右两侧，那么当前节点 root 就是它们的最近公共祖先。
   • 单侧命中：如果只有一个子树返回了非空结果，说明 p 和 q 都在该侧子树中，或者该侧找到了其中一个目标节点。我们将该非空结果向上层返回。
   • 均未命中：返回空。

通过这种“后序遍历”式的递归，我们可以从叶子节点开始向上层反馈信息，直到在某个节点处由于左右两侧同时命中而确立 LCA。

解题思路 (Python)

# 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':
        # 1. 递归终止：找到目标节点或触及叶子节点
        if not root or root is p or root is q:
            return root
        
        # 2. 向左右子树深挖
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        
        # 3. 后序逻辑判断
        # 如果左右都有返回，说明 p, q 分居两侧，当前 root 即为 LCA
        if left and right:
            return root
        
        # 否则，返回非空的那个（代表在单侧找到了目标或找到了 LCA）
        return left or right

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 是二叉树的节点数。在最坏情况下，我们需要遍历整棵树。
• 空间复杂度：$O(N)$。主要开销为递归调用的栈空间深度，最坏情况下等于树的高度（呈链状时为 $N$）。

ACM 模式

本节提供 ACM 竞赛风格的完整可运行代码，包含输入输出处理。

输入格式：

val1 val2 val3 ... valN

输入一行整数数组表示二叉树的层序遍历，None 表示空节点。

完整代码：

import sys

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def build_tree(arr):
    if not arr or arr[0] is None:
        return None
    root = TreeNode(arr[0])
    queue = [root]
    i = 1
    while queue and i < len(arr):
        node = queue.pop(0)
        if arr[i] is not None:
            node.left = TreeNode(arr[i])
            queue.append(node.left)
        i += 1
        if i < len(arr) and arr[i] is not None:
            node.right = TreeNode(arr[i])
            queue.append(node.right)
        i += 1
    return root

def tree_to_list(root):
    if not root:
        return []
    result = []
    queue = [root]
    while queue:
        node = queue.pop(0)
        if node:
            result.append(node.val)
            queue.append(node.left)
            queue.append(node.right)
        else:
            result.append(None)
    while result and result[-1] is None:
        result.pop()
    return result

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
    # 1. 递归终止：找到目标节点或触及叶子节点
    if not root or root is p or root is q:
        return root

    # 2. 向左右子树深挖
    left = self.lowestCommonAncestor(root.left, p, q)
    right = self.lowestCommonAncestor(root.right, p, q)

    # 3. 后序逻辑判断
    # 如果左右都有返回，说明 p, q 分居两侧，当前 root 即为 LCA
    if left and right:
        return root

    # 否则，返回非空的那个（代表在单侧找到了目标或找到了 LCA）
    return left or right

def main():
    arr = sys.stdin.read().strip().split()
    tree_arr = [None if v == 'None' else int(v) for v in arr]
    root = build_tree(tree_arr)

    sol = Solution()
    result = sol.lowestCommonAncestor(root)
    print(result)

if __name__ == "__main__":
    main()