二叉树的最近公共祖先

题目描述
给定一个二叉树和两个节点p、q，要求找到这两个节点在树中的最近公共祖先。最近公共祖先的定义是：对于有根树T的两个节点p、q，最近公共祖先表示为一个节点x，满足x是p、q的祖先且x的深度尽可能大（一个节点也可以是它自己的祖先）。

解题过程

1. 理解问题与示例
   首先，我们需要明确“公共祖先”的含义。假设我们有一个二叉树：

        3
       / \
      5   1
     / \ / \
    6  2 0  8
      / \
     7   4
   

   如果p是节点5，q是节点1，那么它们的最近公共祖先就是根节点3。
   如果p是节点5，q是节点4，那么它们的最近公共祖先是节点5（因为节点5是节点4的祖先）。

2. 分析问题特征
   最近公共祖先（LCA）问题可以通过递归或迭代两种方式解决。递归方法更直观，其核心思想是：

   • 从根节点开始遍历二叉树。
   • 如果当前节点是p或q，则返回当前节点。
   • 如果p和q分别位于当前节点的左右子树中，则当前节点就是LCA。
   • 如果p和q都位于左子树，则在左子树中继续查找；同理，如果都位于右子树，则在右子树中查找。

3. 递归解法步骤

   • 终止条件：如果当前节点为null，或者当前节点就是p或q，则返回当前节点。
   • 递归左子树和右子树：分别对左子节点和右子节点调用递归函数。
   • 判断结果：
     • 如果左子树递归结果为null，说明p和q都在右子树，返回右子树的递归结果。
     • 如果右子树递归结果为null，说明p和q都在左子树，返回左子树的递归结果。
     • 如果左右子树递归结果都不为null，说明p和q分别位于当前节点的左右两侧，当前节点就是LCA，返回当前节点。

4. 代码实现（递归）

   def lowestCommonAncestor(root, p, q):
       if not root or root == p or root == q:
           return root
       left = lowestCommonAncestor(root.left, p, q)
       right = lowestCommonAncestor(root.right, p, q)
       if not left:
           return right
       if not right:
           return left
       return root
   

5. 复杂度分析

   • 时间复杂度：O(n)，其中n是二叉树节点数，最坏情况下需要遍历所有节点。
   • 空间复杂度：O(h)，h为树的高度，递归栈的深度取决于树的高度。

6. 扩展思考
   如果题目中的二叉树是二叉搜索树（BST），可以利用BST的性质（左子树所有节点值小于根节点，右子树所有节点值大于根节点）来简化问题：

   • 如果p和q的值都小于当前节点值，则LCA在左子树。
   • 如果p和q的值都大于当前节点值，则LCA在右子树。
   • 否则，当前节点就是LCA。