在二叉树中寻找两个节点的最近公共祖先（LCA）是一个经典问题，主要分为 普通二叉树 和 二叉搜索树（BST） 两种场景。

1.普通二叉树中寻找最近公共祖先

问题定义

给定一棵普通二叉树和树上的两个节点 p 和 q，请找到它们的最近公共祖先。最近公共祖先被定义为：

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

核心思路

解决这个问题的关键在于利用递归和后序遍历（左 -> 右 -> 根）的特性，从底向上地查找信息。

我们可以为每个节点定义一个递归函数，该函数返回在以当前节点为根的子树中，是否找到了 p 或 q。更具体地说，函数的返回值可以是：

• 如果子树中既没有 p 也没有 q，返回 nullptr。
• 如果子树中只找到了 p，返回 p。
• 如果子树中只找到了 q，返回 q。
• 如果子树中同时找到了 p 和 q，那么当前节点就是 p 和 q 在这棵子树中的最近公共祖先，返回当前节点。

算法步骤分解

1. 递归终止条件：

   • 如果当前节点 root 为 nullptr，说明已经遍历到了树的尽头，返回 nullptr。
   • 如果当前节点 root 就是 p 或者 q，说明我们在当前子树中找到了其中一个目标节点。根据 LCA 的定义，这个节点本身就可能是 LCA（如果另一个节点在它的子树中），所以返回当前节点 root。

2. 递归遍历：

   • 递归地在当前节点的左子树中查找 p 和 q，将结果保存在 left 指针中。
   • 递归地在当前节点的右子树中查找 p 和 q，将结果保存在 right 指针中。

3. 处理返回结果（后序遍历的精髓）：

   • 情况一：left 和 right 都不为 nullptr。
     • 这说明 p 和 q 分别在当前节点的左子树和右子树中找到了。
     • 因此，当前节点 root 就是 p 和 q 的最近公共祖先。返回 root。
   • 情况二：left 不为 nullptr，right 为 nullptr。
     • 这说明在左子树中找到了 p 或 q，但在右子树中什么都没找到。
     • 那么，找到的那个节点（p 或 q）一定在当前节点的左子树中，并且另一个节点也一定在左子树中（否则 right 不会为 nullptr）。
     • 所以，left 指针指向的就是我们要找的 LCA。返回 left。
   • 情况三：left 为 nullptr，right 不为 nullptr。
     • 这与情况二对称。说明在右子树中找到了 LCA。返回 right。
   • 情况四：left 和 right 都为 nullptr。
     • 说明在当前节点的左右子树中都没有找到 p 或 q。返回 nullptr。

C++ 代码实现

二叉树节点的结构：

#include <iostream>
#include <vector>

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    
    // 构造函数
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

实现寻找最近公共祖先的函数：

class Solution {
public:
    
    //root 二叉树的根节点
    //p 目标节点之一
    //q 目标节点之二
    //return p 和 q 的最近公共祖先节点
     
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 1. 递归终止条件
        // 如果当前节点为空，或者当前节点就是 p 或 q，直接返回当前节点
        if (root == nullptr || root == p || root == q) {
            return root;
        }

        // 2. 递归遍历左、右子树
        TreeNode* leftLCA = lowestCommonAncestor(root->left, p, q);
        TreeNode* rightLCA = lowestCommonAncestor(root->right, p, q);

        // 3. 处理返回结果
        // 如果左子树和右子树都找到了非空的结果，说明 p 和 q 分别在两侧，当前节点就是 LCA
        if (leftLCA != nullptr && rightLCA != nullptr) {
            return root;
        }
        
        // 如果只有左子树找到了结果，说明 p 和 q 都在左子树中，返回左子树的结果
        if (leftLCA != nullptr) {
            return leftLCA;
        }

        // 如果只有右子树找到了结果，说明 p 和 q 都在右子树中，返回右子树的结果
        // 如果左右都没找到，rightLCA 也是 nullptr，直接返回即可
        return rightLCA;
    }
};

复杂度分析

• 时间复杂度: O (N)

  • 其中 N 是二叉树的节点总数。在最坏的情况下（例如，树退化为链表），我们需要递归遍历树中的每一个节点一次。

• 空间复杂度: O (H)

  • 其中 H 是二叉树的高度。递归调用会使用函数调用栈，栈的深度取决于树的高度。
  • 在最坏的情况下（链表），H = N，空间复杂度为 O (N)。
  • 在平衡二叉树的情况下，H = log (N)，空间复杂度为 O (log (N))。

这种递归方法是解决普通二叉树 LCA 问题的标准且最高效的方法。

2.二叉搜索树（BST）中的最近公共祖先（LCA）

二叉搜索树的特性使得寻找最近公共祖先的过程比普通二叉树更高效、更简单。

问题定义

给定一棵二叉搜索树（BST）和树上的两个节点 p 和 q，请找到它们的最近公共祖先。

核心思路：利用 BST 的特性

BST 的核心特性是：对于树中的任意一个节点，其左子树中的所有节点的值都小于它，右子树中的所有节点的值都大于它。

这个特性是解决问题的关键。我们可以从根节点开始，根据 p 和 q 的值与当前节点值的大小关系，来决定搜索的方向：

1. 如果当前节点的值 root->val 同时大于 p->val 和 q->val：

   • 这说明 p 和 q 都在当前节点的左子树中。
   • 因此，它们的最近公共祖先也一定在左子树中。我们需要继续向左子树深处搜索。

2. 如果当前节点的值 root->val 同时小于 p->val 和 q->val：

   • 这说明 p 和 q 都在当前节点的右子树中。
   • 因此，它们的最近公共祖先也一定在右子树中。我们需要继续向右子树深处搜索。

3. 如果上述两种情况都不成立：

   • 这说明 p 和 q 分别在当前节点的两侧（一个在左，一个在右），或者其中一个节点就是当前节点本身。
   • 在这种情况下，当前节点 root 就是 p 和 q 的最近公共祖先。

为什么第三种情况时当前节点就是 LCA？

• 情况 A (分属两侧)：p 在左，q 在右。那么从 p 到 q 的路径必须经过它们的根节点，也就是当前节点。同时，由于我们是从上往下搜索，这是第一个满足此条件的节点，所以它一定是 “最近” 的。
• 情况 B (其中一个是当前节点)：假设 p == root。那么 p 就是 q 的祖先（因为 q 在 p 的左或右子树中）。根据 LCA 的定义，一个节点可以是它自己的祖先，所以 p (即 root) 就是 LCA。

C++ 代码实现

#include <iostream>
#include <vector>

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    
    // 构造函数
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

//迭代法
class Solution {
public:
    
     //root 二叉搜索树的根节点
     //p 目标节点之一
     //q 目标节点之二
     //return p 和 q 的最近公共祖先节点
     
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 从根节点开始遍历
        TreeNode* current = root;
        
        while (current != nullptr) {
            // 情况 1: p 和 q 都在当前节点的左子树
            if (current->val > p->val && current->val > q->val) {
                current = current->left;
            }
            // 情况 2: p 和 q 都在当前节点的右子树
            else if (current->val < p->val && current->val < q->val) {
                current = current->right;
            }
            // 情况 3: 找到 LCA
            else {
                return current;
            }
        }
        
        // 如果树为空或节点不在树中，返回 nullptr
        return nullptr;
    }
};

复杂度分析

• 时间复杂度: O (H)

  • 其中 H 是二叉搜索树的高度。在最坏的情况下（树退化为链表），时间复杂度为 O (N)。但对于平衡的 BST，时间复杂度为 O (log N)。每一次迭代或递归调用都会使我们向目标节点靠近一步。

• 空间复杂度:

  • O (1)。我们只使用了有限几个指针变量。

总结

与普通二叉树的 LCA 问题相比，BST 的 LCA 问题因为其有序性而变得非常高效。我们不需要像在普通二叉树中那样后序遍历整棵树来收集信息，而是可以利用 BST 的特性，从根节点开始进行一次自上而下的遍历，就能准确地定位到最近公共祖先。迭代法是解决此问题的最优选择，因为它实现简单且空间效率极高。