二叉树最近的公共祖先

以下是两种求二叉树最近公共祖先的方法：

1. 递归法

递归法是一种比较直观的方法，对于当前节点，如果它的左子树或右子树中包含p或q，则返回当前节点，否则继续递归左右子树。

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root or root == p or root == q:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left and right:
            return root
        return left if left else right

2. 迭代法

迭代法使用栈来模拟递归过程，对于每个节点，将它的父节点和深度一起入栈，然后不断弹出栈顶元素，如果当前节点的左子树或右子树中包含p或q，则返回当前节点，否则继续遍历。

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        stack = [(root, None)]
        parent = {root: None}
        depth = 0
        while p not in parent or q not in parent:
            node, par = stack.pop()
            if node.left:
                parent[node.left] = node
                stack.append((node.left, node))
            if node.right:
                parent[node.right] = node
                stack.append((node.right, node))
        ancestors = set()
        while p:
            ancestors.add(p)
            p = parent[p]
        while q not in ancestors:
            q = parent[q]
        return q