K12048 最近祖先c++

K12048 最近祖先是一道经典的算法题目，用于求解给定两个节点在一棵树上的最近公共祖先。这个问题的解法有很多，其中比较常见的是 Tarjan 算法和倍增算法。

Tarjan 算法使用深度优先搜索遍历整棵树，对于每个节点，记录其祖先节点的信息，然后使用并查集来维护每个节点所在的连通块。在查询最近公共祖先时，根据两个节点的祖先信息，利用并查集的路径压缩和按秩合并优化，即可快速求出它们的最近公共祖先。

倍增算法则是利用了树的性质，通过预处理出每个节点的 2^k 级祖先，来快速查询两个节点的最近公共祖先。具体来说，对于每个节点，预处理出其 1、2、4、8、16……2^k 级祖先的信息，然后在查询两个节点的最近公共祖先时，先将它们调整到同一深度，然后从深度最大的开始逐层向上跳，直到找到一个节点，使得两个节点都在其下面。

相关问题

设一棵有 n ( n ≤100）个结点的二叉树按顺序存储方式存储在 bt [1.. n ］中，编写算法，求二叉树中编号为 i 和 j 的两个结点的最近公共祖先结点。

对于这种二叉树的顺序存储问题，我们可以利用线索二叉树（Threaded Binary Tree）的思想。线索二叉树是一种特殊的二叉搜索树，每个节点除了常规的左右孩子指针外，还额外有两个线索，分别指向其前驱节点和后继节点。这样在遍历时就可以方便地跳过非搜索路径上的节点，从而简化了寻找最近公共祖先（LCA）的操作。

对于寻找编号为i和j的两个节点的最近公共祖先，首先我们需要确定它们在二叉搜索树中的位置，即需要找到它们对应的最小值和最大值。一旦我们有了这两个范围的边界，我们可以在中序遍历中找到LCA，因为中序遍历的顺序正是升序排列的。

以下是C++伪代码示例：

TreeNode* findLCA(TreeNode* bt[], int i, int j) {
    // 找到i和j的最小值和最大值对应的节点
    TreeNode* minNode = nullptr;
    for (int k = 1; k <= n && !minNode; ++k) {
        if (bt[k].val >= i) {
            minNode = bt[k];
        }
    }

    TreeNode* maxNode = nullptr;
    for (int k = n; k >= 1 && !maxNode; --k) {
        if (bt[k].val <= j) {
            maxNode = bt[k];
        }
    }

    // 从最小值开始，如果遇到大于等于j的节点就往上走，直到找到maxNode
    TreeNode* lca = minNode;
    while (lca != nullptr && lca->val < j) {
        if (lca->right线索指向的节点 && lca->right线索->val >= j) {
            lca = lca->right线索;
        } else {
            lca = lca->parent;
        }
    }

    // 类似地，从最大值开始，如果遇到小于等于i的节点就往回走，直到找到minNode
    while (lca != nullptr && lca->val > i) {
        if (lca->left线索指向的节点 && lca->left线索->val <= i) {
            lca = lca->left线索;
        } else {
            lca = lca->parent;
        }
    }

    return lca;
}

这里假设bt数组表示了线索二叉树的结构，每个节点都有一个parent、left线索和right线索。注意，这个代码仅适用于二叉搜索树的情况下，因为其他类型的二叉树可能无法直接提供最近公共祖先的信息。