在一颗二叉树中寻找p和q的最近公共祖先结点

Question

请问这两个代码运行结果一样嘛，第一个代码可不可以把s1，s2只看做数组而不是栈来操作呀

Answer 1

回复不易，麻烦关注下博主，后面还有问题直接私信我，谢谢！！！

在一颗二叉树中寻找两个结点 p 和 q 的最近公共祖先（Lowest Common Ancestor，LCA）是一个经典的二叉树问题。以下是一种常见的解决方法，使用递归进行深度优先搜索（DFS）：

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

def lowestCommonAncestor(root, p, q):
    # 如果当前节点为空，返回 None
    if not root:
        return None

    # 如果当前节点是 p 或 q 中的一个，直接返回当前节点
    if root == p or root == q:
        return root

    # 在左子树中递归查找 p 和 q 的最近公共祖先
    left_lca = lowestCommonAncestor(root.left, p, q)

    # 在右子树中递归查找 p 和 q 的最近公共祖先
    right_lca = lowestCommonAncestor(root.right, p, q)

    # 如果左子树和右子树分别找到了 p 和 q，说明当前节点就是最近公共祖先
    if left_lca and right_lca:
        return root

    # 如果只在左子树或右子树找到了 p 或 q，则继续向上返回找到的节点
    return left_lca or right_lca

这个算法的思路是通过递归深度优先搜索遍历整棵二叉树，查找包含结点 p 或 q 的路径。当找到 p 或 q 时，直接返回该结点；如果在左子树和右子树中都找到了 p 或 q，说明当前节点是最近公共祖先。如果只在左子树或右子树找到了一个结点，继续向上返回找到的结点。这样，通过递归遍历整棵树，最终找到了 p 和 q 的最近公共祖先。