题解 | #农场牛群族谱#

农场牛群族谱

https://www.nowcoder.com/practice/7d28855a76784927b956baebeda31dc8

知识点：

二叉树/LCA

分析：

使用二进制的思想，对二叉树进行预处理，得到一个fa数组；同时记录每一个节点的深度depth；

那么为什么就可以这么做呢？首先这个方法是ologn的复杂度

首先，大家需要理解二进制凑数：

例如：（2^0 ~ 2^4）1 2 4 8 16 凑出 11，如何来凑呢，

首先从高位判断，11 < 16,不选16
11 >= 8, 选 8 余 3
3 <= 4 ,不选4
3 >= 2,选2 余1
1 >= 1,选1

所以（11）₁₀=（1011）_2.

倍增法LCA，分为两步：

把两个点跳到同一层把p跳到和q同一层 depth相等即可
在depth(x)==depth(y)后一起往上跳2^k步
在这个过程中，可能 p == q ,那么 p或q随便哪一个就是他们最近公共祖先
p != q , 同层但不同, 则继续让两个点同时往上跳一直跳到它们的最近公共祖先的下一层

进一步：

即p,q从同一高度同时起跳后,在f[p][0]!=f[q][0] 的约束下我们能跳的最多的步数跳完后 p,q就达到了LCA的下面一层假定我们知道p,q出发点为第1层，LCA下一层为第12层,那么最多能跳的步数t = 12-1 = 11 = (1011)2 = 最多能跳2^3 + 2^2 + 2^0 步,所以我们就通过从大到小枚举k使得我们刚好跳11步而不能跳超过12步,但实际上我们并不知道要跳11步,所以我们可以通过f[p][0]!=f[q][0]的约束来实现
预处理中fa数组，f(i, j) 是i开始向上走2的j次方步所走到的节点

举个例子：

f[6][0] = 4

f[6][1] = 2

f[6][2] = /

为什么最后跳到最近公共祖先的下一层？方便判断假如f[p][k] == f[q][k] <=> f[p][k] 或者 f[q][k]是p和q的一个公共祖先但不一定是最近的。
为什么fa[j][k] = fa[fa[j][k - 1]][k - 1];

j>0 f[i][j-1]

父亲的父亲就是爷爷, 爷爷的爷爷就是4倍祖先

编程语言：

C++

完整代码：

    struct Node {
        TreeNode* node;
        int depth;
    };
    static const int N = 45;
    vector<int> tree[N];
    int fa[N][20];
    int depth[N];
    Node q[N];
    void bfs(TreeNode* root) {
        if (root == nullptr) {
            return;
        }
        memset(depth, 0x3f, sizeof depth);
        depth[0] = 0;
        depth[root->val] = 1;
        int hh = 0, tt = -1;
        q[++tt] = {root, 1};
        while (hh <= tt) {
            Node cur = q[hh++];
            TreeNode* t = cur.node;
            int d = cur.depth;
            if (t->left) {
                TreeNode* leftChild = t->left;
                int j = leftChild->val;
                if (depth[j] > d + 1) {
                    depth[j] = d + 1;
                    q[++tt] = {leftChild, d + 1};
                    fa[j][0] = t->val;
                    for (int k = 1; k <= 15; k++) {
                        fa[j][k] = fa[fa[j][k - 1]][k - 1];
                    }
                }
            }
            if (t->right) {
                TreeNode* rightChild = t->right;
                int j = rightChild->val;
                if (depth[j] > d + 1) {
                    depth[j] = d + 1;
                    q[++tt] = {rightChild, d + 1};
                    fa[j][0] = t->val;
                    for (int k = 1; k <= 15; k++) {
                        fa[j][k] = fa[fa[j][k - 1]][k - 1];
                    }
                }
            }
        }
    }
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
        bfs(root);
        if (depth[p] < depth[q]) swap(p, q);
        for (int k = 15; k >= 0; k--) {
            if (depth[fa[p][k]] >= depth[q]) p = fa[p][k];
        }
        if (p == q) return q;
        for (int k = 15; k >= 0; k--) {
            if (depth[fa[p][k]] != depth[fa[q][k]]) {
                p = fa[p][k];
                q = fa[q][k];
            }
        }
        return fa[q][0];
    }