最近公共祖先

待我称王封你为后i 2023-06-13 14:25 1阅读 0赞

> 语言： C++
> 
> **题目描述 :**
> 
> 有一棵无穷大的满二叉树，其结点按根结点一层一层地从左往右依次编号，根结点编号为1。现在有两个结点a，b。请设计一个算法，求出a和b点的最近公共祖先的编号。
> 
> 给定两个int **a**,**b**。为给定结点的编号。请返回**a**和**b**的最近公共祖先的编号。注意这里结点本身也可认为是其祖先。
> 
> 测试样例：
> 
> 输入
> 
>     2 3
> 
> 返回 1 
> 
> 给定接口
> 
>     class LCA {
>     public:
>         int getLCA(int a, int b) {
>     
>         }
>     };
> 
> OJ链接：[https://www.nowcoder.com/questionTerminal/70e00e490b454006976c1fdf47f155d9?toCommentId=4964723][https_www.nowcoder.com_questionTerminal_70e00e490b454006976c1fdf47f155d9_toCommentId_4964723]  
> 来源：牛客网

> **分析 :**
> 
> **思路1: **
> 
> 这道题不同与一般二叉树题目的是, 题目中并没有一个真正的二叉树, 寻找公共祖先并不是通过遍历二叉树来实现 ,而是在熟
> 
> 悉二叉树的的基础上发现规律.  题中所给出的二叉树模型实际上是一个完全二叉树, 如下 :
> 
> ![format_png][]
> 
> 如果足够了解过堆这种数据结构, 会发现这其实是一个特殊的堆, (不了解也不妨碍做这道题, 仔细观察也可以看出同样的的
> 
> 规律)堆在逻辑上是一颗二叉树, 物理(存储结构)上是一个顺序表那么在这个顺序表的中左右孩子的下标和父亲节点的下标是
> 
> 有规律的, 如某个节点下标为 n , 那么它的左孩子下标为 2n+1右孩子下标为2n+2, 它的父亲节点下标为 (int)(n - 1) / 2, 在本
> 
> 题中每个节点的编号正好是下标加 1 ,这就更好办了, 某个节点的编号为n, 那么它的父亲节点编号就又下标公式可得为
> 
> (n+1-1) / 2 = (int) n / 2, 有了这个公式就可以很方便的直接遍历祖先节点了 .
> 
> 那么这道题的思路就清晰了,在遍历祖先节点的过程中比较
> 
> 祭出代码

#include<iostream>
    using namespace std;
    
    class LCA {
    public:
        int getLCA(int a, int b) {
            while (a != b) { 
                a > b ? a /= 2: b /= 2;
            }
            return a;
        }
    };
    int main() {
        LCA l;
        int a, b;
        while (cin >> a >> b) {
            cout << l.getLCA(a, b)<< endl;
        }
        system("pause");
        return 0;
    }

> **思路2 : **
> 
> 这种思路就很清奇了, 再看来看一下这棵树
> 
> ![format_png][]
> 
>  这棵树的父亲节点和左右孩子节点的值,  在二进制下有个规律,  比如说父亲节点1 和 左右孩子2, 3
> 
> 二进制是 1 , 10, 11.  父节点4和左右孩子8,9二进制是, 100, 1000, 1001.  能够发现, 左孩子节点在是父节点左移1位的结果,
> 
> 右孩子是左孩子加1 . 再来看11的二进制, 1011, 4的二进制100, 他们的最近祖先节点是2 , 2的二进制是 10
> 
> 再来看12和15, 他们的最近公共祖先是3, 二进制分别是1100, 1111, 11 .   
> 
>        ![format_png 1][]    ![20191117210904775.png][]    ![format_png 2][] ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70][]
> 
> 现在, 规律应该一目了然了, 两个数的二进制的有效部分(除去前面是全是0的位数)重叠的那部分, 就是最近公共祖先
> 
> 这次真是祭出代码了

#include<iostream>
    using namespace std;
    class LCA {
    public:
        int getLCA(int a, int b) {
            int i, j, ancestor = 0;
            for (i = 31; !((a >> i) & 1); --i);
            for (j = 31; !((b >> j) & 1); --j);
            if (i == 0 || j == 0) return 1;
            for (; i >= 0 && j >= 0 && ((a >> i) & 1) == ((b >> j) & 1); --i, --j) {
                ancestor <<= 1;
                ancestor += ((a >> i) & 1);
            }
            return ancestor;
        }
    int main() {
        LCA l;
        int a, b;
        while (cin >> a >> b) {
            cout << l.getLCA(a, b)<< endl;
        }
        system("pause");
        return 0;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 1][]

[https_www.nowcoder.com_questionTerminal_70e00e490b454006976c1fdf47f155d9_toCommentId_4964723]: https://www.nowcoder.com/questionTerminal/70e00e490b454006976c1fdf47f155d9?toCommentId=4964723
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly90aW1nc2EuYmFpZHUuY29tL3RpbWc_aW1hZ2UmcXVhbGl0eT04MCZzaXplPWI5OTk5XzEwMDAwJnNlYz0xNTc0MDAyODAyNzUwJmRpPTk4NGU3ZWJhMDZhZWMyOGE3Yzc2ZjhmMjRlMzhiODk0JmltZ3R5cGU9MCZzcmM9aHR0cCUzQSUyRiUyRmdzczAuYmFpZHUuY29tJTJGLXZvM2RTYWdfeEk0a2hHa285V1RBbkY2aGh5JTJGemhpZGFvJTJGcGljJTJGaXRlbSUyRjg2MDFhMThiODdkNjI3N2ZjMzhjYjM4YzJkMzgxZjMwZTgyNGZjZWMuanBn?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly90aW1nc2EuYmFpZHUuY29tL3RpbWc_aW1hZ2UmcXVhbGl0eT04MCZzaXplPWI5OTk5XzEwMDAwJnNlYz0xNTc0MDA2MTQyNDY3JmRpPWVkMTQ5NzMxYzYwY2Y4ZTRmZDFmMDU3NTcyNzU0OGUzJmltZ3R5cGU9MCZzcmM9aHR0cCUzQSUyRiUyRnBpYzEud2luNDAwMC5jb20lMkZwaWMlMkY4JTJGOTIlMkYzYTUyODMzMTEyXzEzMF8xNzAuanBn?x-oss-process=image/format,png
[20191117210904775.png]: https://img-blog.csdnimg.cn/20191117210904775.png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zczEuYmRzdGF0aWMuY29tLzcwY0Z2WFNoX1ExWW54R2twb1dLMUhGNmhoeS9pdC91PTM0NTMwNDQxMDUsNzAwNDc1MDg0JmZtPTI2JmdwPTAuanBn?x-oss-process=image/format,png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191117210712950.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2019111721261044.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMDcxMDY4,size_16,color_FFFFFF,t_70