如何通过变量路径回溯定位二叉树的公共祖先节点

二叉树最近公共祖先查找的核心思路

二叉树的最近公共祖先指的是两个指定节点在树中共同的最近父节点，要定位这个节点，核心是先分别找到从根节点到两个目标节点的完整路径，再通过比对两条路径找到最后一个相同的节点，这个节点就是最近公共祖先。

路径记录的实现逻辑

我们可以采用深度优先遍历的方式，在遍历过程中用一个变量存储当前走过的节点路径，当找到目标节点时，就把当前路径保存下来。这里用递归实现会更清晰，递归进入节点时把节点加入路径，递归退出时把节点从路径移除，保证路径记录的正确性。

路径查找的代码实现

以下是用Python实现的路径查找函数，通过递归遍历二叉树，找到目标节点后返回对应的路径列表：

def find_path(root, target, current_path, result):
    # 如果当前节点为空，直接返回
    if not root:
        return
    # 将当前节点加入路径
    current_path.append(root.val)
    # 如果找到目标节点，将当前路径的拷贝存入结果
    if root.val == target:
        result.append(current_path.copy())
    # 递归遍历左子树和右子树
    find_path(root.left, target, current_path, result)
    find_path(root.right, target, current_path, result)
    # 回溯时移除当前节点，恢复路径状态
    current_path.pop()

# 二叉树节点的定义
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

双路径比对定位公共祖先

得到两个目标节点的路径后，我们需要从路径的第一个元素开始比对，找到最后一个相同的节点。因为路径的第一个元素都是根节点，所以只要两条路径出现第一个不同的元素，前一个元素就是最近公共祖先。

公共祖先查找的完整代码

结合路径查找和路径比对的逻辑，完整的查找函数如下：

def lowest_common_ancestor(root, p, q):
    # 存储两个目标节点的路径
    path_p = []
    path_q = []
    # 查找节点p的路径
    find_path(root, p, [], path_p)
    # 查找节点q的路径
    find_path(root, q, [], path_q)
    # 如果没有找到两个节点的路径，返回None
    if not path_p or not path_q:
        return None
    # 取第一条找到的路径即可，因为二叉树中节点值唯一的话路径唯一
    p_path = path_p[0]
    q_path = path_q[0]
    # 比对两条路径，找到最后一个相同的节点
    common_ancestor = None
    for i in range(min(len(p_path), len(q_path))):
        if p_path[i] == q_path[i]:
            common_ancestor = p_path[i]
        else:
            break
    return common_ancestor

# 测试示例
if __name__ == "__main__":
    # 构建测试二叉树：根节点3，左子树5（左1，右2），右子树8（左7，右4）
    node1 = TreeNode(1)
    node2 = TreeNode(2)
    node5 = TreeNode(5, node1, node2)
    node7 = TreeNode(7)
    node4 = TreeNode(4)
    node8 = TreeNode(8, node7, node4)
    root = TreeNode(3, node5, node8)
    # 查找节点1和节点2的最近公共祖先
    result = lowest_common_ancestor(root, 1, 2)
    print("节点1和节点2的最近公共祖先是：", result)
    # 查找节点1和节点7的最近公共祖先
    result2 = lowest_common_ancestor(root, 1, 7)
    print("节点1和节点7的最近公共祖先是：", result2)

逻辑优化与注意事项

上述实现假设二叉树中节点的值是唯一的，如果存在重复值，路径查找的逻辑需要调整，比如改用节点对象本身作为比对依据，而不是节点值。另外，递归遍历的路径回溯逻辑是核心，一定要保证节点加入路径和移除路径的顺序正确，否则会出现路径记录错误的问题。

如果二叉树是二叉搜索树，还可以利用二叉搜索树的有序性优化查找逻辑，不需要存储完整路径，只需要在遍历过程中判断当前节点的值和两个目标节点值的大小关系即可，能大幅降低空间复杂度。

binary_treelowest_common_ancestorpath_backtrackingnode_traversal修改时间：2026-06-29 09:09:13