首页 > 试题广场 >

在二叉树中找到两个节点的最近公共祖先(再进阶)

[编程题]在二叉树中找到两个节点的最近公共祖先(再进阶)
  • 热度指数:595 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一棵二叉树,多次给出这棵树上的两个节点 o1 和 o2,请对于每次询问,找到 o1 和 o2 的最近公共祖先节点。

输入描述:
第一行输入两个整数 n 和 root,n 表示二叉树的总节点个数,root 表示二叉树的根节点。
以下 n 行每行三个整数 fa,lch,rch,表示 fa 的左儿子为 lch,右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子,rch同理)
第 n+2 行输入一个整数 m,表示询问的次数。
以下 m 行每行两个节点 o1 和 o2。


输出描述:
对于每组询问每行输出一个整数表示答案。
示例1

输入

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

输出

2
2
3
1

备注:



#include<bits/stdc++.h>
using namespace std;
struct Node{
    int lc = 0;
    int rc = 0;
    int parent = -1;
    int level;
};
// 确定每个结点所在层
void getNodeLevel(vector<Node>& tree,int root)
{
    if(!root) return;
    // 左子树各节点的level
    if(tree[root].lc)
    {
        tree[tree[root].lc].level = tree[root].level + 1;
        getNodeLevel(tree,tree[root].lc);
    }
    // 右子树各节点的level
    if(tree[root].rc)
    {
        tree[tree[root].rc].level = tree[root].level + 1;
        getNodeLevel(tree,tree[root].rc);
    }
    // 设置根节点的level
    if(tree[root].parent == -1) 
        return;
    tree[root].level  = tree[tree[root].parent].level + 1;
}
int LCA(vector<Node>& tree,int o1,int o2)
{
    // 把层次深的节点一直沿父节点上移 直到两个节点处于同一level
    // 同一层次的节点同时沿各自的父节点上移,第一个相遇的节点就是LCA
    while(o1 != o2)
    {
        if(tree[o1].level>tree[o2].level)
            o1 = tree[o1].parent;
        else if(tree[o1].level<tree[o2].level)
            o2 = tree[o2].parent;
        else
        {
            o1 = tree[o1].parent;
            o2 = tree[o2].parent;
        }
    }
    return o1;
}
int main()
{
    int n,root;
    cin>>n>>root;
    vector<Node>tree(n+1);
    int pa,l,r;
    for(int i=0;i<n;++i)
    {
        cin>>pa;
        cin>>l>>r;
        tree[pa].lc = l;
        tree[pa].rc = r;
        if(l) tree[l].parent = pa;
        if(r) tree[r].parent = pa;
    }
    getNodeLevel(tree,root);
    int m;
    int o1,o2;
    cin>>m;
    while(m--)
    {
        cin>>o1>>o2;
        cout<<LCA(tree,o1,o2)<<endl;
    }

}
发表于 2020-02-07 11:25:41 回复(1)