EC09-在二叉树中找到节点p和q的最近公共祖先¶

代码实现¶

链式存储¶

C
// 函数 find_LCA：在二叉树中找到节点 p 和 q 的最近公共祖先
// 参数：root - 二叉树根节点，p - 目标节点1，q - 目标节点2
BiTree find_LCA(BiTree root, BiTree p, BiTree q) {
    // 递归终止条件
    if (root == NULL || root == p || root == q) {
        return root; // 如果根节点为空或等于其中一个目标节点，则返回根节点
    }

    // 递归在左右子树中查找
    BiTree left = find_LCA(root->lchild, p, q);   // 在左子树中查找
    BiTree right = find_LCA(root->rchild, p, q);  // 在右子树中查找

    // 根据左右子树的查找结果判断最近公共祖先
    if (left == NULL && right == NULL) {
        // 左右子树都没有找到 p 或 q
        return NULL;
    }

    if (left != NULL && right != NULL) {
        // p 和 q 分别在左右子树中，当前根节点就是最近公共祖先
        return root;
    }

    // p 和 q 都在左子树或右子树中，返回非空的那一侧结果
    return left != NULL ? left : right;
}

顺序存储¶

C
// 函数 find_LCA：在顺序存储的完全二叉树中找到节点的最近公共祖先，数组下标从0开始
// 参数：aa - 顺序存储的数组，i - 节点 p 的数组下标，j - 节点 q 的数组下标
BiTree find_LCA(BiTree aa[], int i, int j) {
    // 通过不断向上移动到父节点，直到两个节点相遇
    while (i != j) {
        if (j > i) {
            // j 节点更深，向上移动到父节点
            j = (j - 1) / 2;
        } else {
            // i 节点更深，向上移动到父节点
            i = (i - 1) / 2;
        }
    }

    // 当 i == j 时，找到了最近公共祖先
    return aa[i];
}

代码逻辑解析¶

1. 链式存储的 LCA 算法¶

递归思路：¶

使用后序遍历的思想： - 先在左右子树中查找目标节点 - 根据查找结果判断最近公共祖先的位置

四种情况分析：¶

C
// 情况1：当前节点为空或就是目标节点
if (root == NULL || root == p || root == q)
    return root;

// 情况2：左右子树都没找到目标节点
if (left == NULL && right == NULL)
    return NULL;

// 情况3：目标节点分别在左右子树中
if (left != NULL && right != NULL)
    return root;  // 当前节点就是最近公共祖先

// 情况4：目标节点都在同一侧子树中
return left != NULL ? left : right;

2. 顺序存储的 LCA 算法¶

核心思想：¶

利用完全二叉树的性质： - 对于下标为 i 的节点，其父节点下标为 (i-1)/2 - 通过不断向上移动，两个节点最终会在最近公共祖先处相遇

移动策略：¶

C
while (i != j) {
    if (j > i) 
        j = (j - 1) / 2;  // j 节点更深，向上移动
    else 
        i = (i - 1) / 2;  // i 节点更深，向上移动
}

时间复杂度分析¶

1. 链式存储版本¶

最坏情况分析：¶

需要遍历整棵树的所有节点
每个节点最多被访问一次
时间复杂度：O(n)

最好情况分析：¶

如果两个目标节点都在靠近根部的位置
可能提前返回，但最坏情况仍需遍历

2. 顺序存储版本¶

分析过程：¶

每次迭代都将较深的节点向上移动一层
树的高度为 log n（完全二叉树）
最多需要 log n 次迭代
时间复杂度：O(log n)

空间复杂度分析¶

1. 链式存储版本¶

递归调用栈：¶

递归深度取决于树的高度
最好情况（平衡树）：O(log n)
最坏情况（退化为链表）：O(n)
空间复杂度：O(h)，其中 h 是树的高度

2. 顺序存储版本¶

额外空间使用：¶

只使用了常量级别的局部变量（i, j）
没有递归调用
空间复杂度：O(1)

较难理解部分的说明¶

1. 链式存储算法的核心思想¶

C
// 递归返回值的含义：
// NULL：在以当前节点为根的子树中没有找到 p 或 q
// p/q：在以当前节点为根的子树中找到了 p 或 q
// root：在以当前节点为根的子树中，root 是 p 和 q 的最近公共祖先

// 示例分析：
//        1
//       / \
//      2   3
//     /   / \
//    4   5   6
//   /
//  7

// 查找节点 4 和 6 的 LCA：
// find_LCA(1, 4, 6):
//   left = find_LCA(2, 4, 6) = 2  // 4 在左子树
//   right = find_LCA(3, 4, 6) = 3 // 6 在右子树
//   left != NULL && right != NULL → return 1

2. 顺序存储算法的数学原理¶

C
// 完全二叉树的性质：
// 节点编号从 0 开始，对于节点 i：
// 父节点：(i-1)/2
// 左子节点：2*i+1
// 右子节点：2*i+2

// 路径追溯示例：
// 假设节点下标：i=7, j=5
// 路径：
// 7 → 3 → 1 → 0
// 5 → 2 → 1 → 0
// 在节点 1 处相遇，所以 LCA 是节点 1

3. 图解说明¶

链式存储算法示例：¶

Text Only

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

查找节点 5 和 1 的 LCA：
1. find_LCA(3, 5, 1)
2. left = find_LCA(5, 5, 1) = 5  // 找到 5
3. right = find_LCA(1, 5, 1) = 1 // 找到 1
4. left != NULL && right != NULL → return 3

顺序存储算法示例：¶

Text Only

数组表示的完全二叉树：
索引: 0  1  2  3  4  5  6
节点: 3  5  1  6  2  0  8

查找节点 6(索引3) 和 0(索引5) 的 LCA：
初始：i=3, j=5
第1轮：j > i → j = (5-1)/2 = 2
第2轮：i < j → i = (3-1)/2 = 1
第3轮：i > j → j = (2-1)/2 = 0
第4轮：i > j → j = (1-1)/2 = 0
第5轮：i = j = 0 → 返回 aa[0] = 3

延伸知识点¶

1. 链式存储的优化版本¶

C
// 带路径记录的 LCA 算法
bool findPath(BiTree root, BiTree target, vector<BiTree>& path) {
    if (root == NULL) return false;

    path.push_back(root);

    if (root == target) return true;

    if (findPath(root->lchild, target, path) || 
        findPath(root->rchild, target, path)) {
        return true;
    }

    path.pop_back();
    return false;
}

BiTree find_LCA_path(BiTree root, BiTree p, BiTree q) {
    vector<BiTree> path1, path2;

    if (!findPath(root, p, path1) || !findPath(root, q, path2)) {
        return NULL;
    }

    // 找到两条路径的第一个分叉点
    int i = 0;
    while (i < path1.size() && i < path2.size() && path1[i] == path2[i]) {
        i++;
    }

    return path1[i-1];
}

2. Tarjan 离线 LCA 算法¶

C
// 使用并查集的 Tarjan 算法（处理多个查询）
class UnionFind {
private:
    vector<int> parent, rank;
public:
    UnionFind(int n) : parent(n), rank(n, 0) {
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }

    void unite(int x, int y) {
        int rootX = find(x), rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY]) {
                swap(rootX, rootY);
            }
            parent[rootY] = rootX;
            if (rank[rootX] == rank[rootY]) {
                rank[rootX]++;
            }
        }
    }
};

3. RMQ 转化为 LCA¶

C
// 通过欧拉序列将 LCA 问题转化为 RMQ 问题
class LCA_RMQ {
private:
    vector<int> euler, depth, first;
    SparseTable st; // 稀疏表用于 RMQ

public:
    void dfs(BiTree root, int d) {
        first[root->val] = euler.size();
        euler.push_back(root->val);
        depth.push_back(d);

        if (root->lchild) {
            dfs(root->lchild, d + 1);
            euler.push_back(root->val);
            depth.push_back(d);
        }

        if (root->rchild) {
            dfs(root->rchild, d + 1);
            euler.push_back(root->val);
            depth.push_back(d);
        }
    }

    int query(int u, int v) {
        int left = first[u], right = first[v];
        if (left > right) swap(left, right);
        return st.query(left, right); // 返回深度最小的节点
    }
};

4. 实际应用场景¶

文件系统：查找两个文件的最近公共目录
社交网络：查找两个人的最近公共好友
版本控制：Git 中查找两个提交的最近公共祖先
网络路由：在网络拓扑中查找两个节点的最近公共路由器
编译器优化：在抽象语法树中查找表达式的公共子表达式

5. 算法对比总结¶

算法类型	时间复杂度	空间复杂度	适用场景
递归遍历	O(n)	O(h)	通用二叉树
顺序存储	O(log n)	O(1)	完全二叉树
路径记录	O(n)	O(h)	需要路径信息
Tarjan	O(n+q)	O(n)	多次查询
RMQ转化	O(nlogn)预处理，O(1)查询	O(nlogn)	大量查询

这两种 LCA 算法展示了根据数据结构特性选择合适算法的重要思想，顺序存储的优化体现了利用数据特性提升算法效率的设计理念。