版权声明 本站原创文章 由 萌叔 发表
转载请注明 萌叔 | http://vearne.cc

题目

查找二叉树的最近公共祖先
示例如下:
图示

  1. 节点6和节点8的最近公共祖先是节点4
  2. 节点2和节点5的最近公共祖先也是节点0
  3. 节点4和节点7的最近公共祖先也是节点4

思路

1)采用中序遍历(先左子树-> 根 -> 右子树)
可以得到每个节点在树中的层级
2)扫描2个目标节点之间所有节点,层级最小的节点,即为最近公共祖先

ancestor.cpp

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
#define MAX_VALUE  1000000
struct node{
int data;
struct node* lchild;
struct node* rchild;
};
typedef struct node Node;
int levels[100];
int lca(Node* root,int m,int n){
    Node* p = root;
    vector<int> v;
    stack<Node*> s;
    int level = 0;
    cout<<"中序遍历:"<<endl;
    while(p||!s.empty()){
        if(p){
            s.push(p);
            levels[p->data]=level;
            p = p->lchild;
            level++;
        }else{
            p = s.top();
            level = levels[p->data];
            s.pop();
            cout<<p->data<<" ";
            v.push_back(p->data);
            p = p->rchild;
            level++;
        }
    }
    cout<<endl;
    cout<<"节点对应层级:"<<endl;
    for(int i=0;i<v.size();i++){
        cout<<levels[v[i]]<<" ";
    }
    cout<<endl;
    int minLevel = MAX_VALUE;
    int res = -1;
    bool flag = false;
    for(int i=0;i<v.size();i++){
        if(v[i]==m||v[i]==n){
            if(levels[v[i]]<minLevel){
                res = v[i];
                minLevel = levels[v[i]];
            }
            flag = !flag;
        }else if(flag){
            if(levels[v[i]]<minLevel){
                res = v[i];
                minLevel = levels[v[i]];
            }
        }

    }
    return res;
}
int main(){
    Node node0={0,NULL,NULL};
    Node node1={1,NULL,NULL};
    Node node4={4,NULL,NULL};
    Node node2={2,NULL,NULL};
    Node node3={3,NULL,NULL};
    Node node5={5,NULL,NULL};
    Node node6={6,NULL,NULL};
    Node node7={7,NULL,NULL};
    Node node8={8,NULL,NULL};
    node0.lchild = &node1;
    node0.rchild = &node4;
    node1.lchild = &node2;
    node1.rchild = &node3;
    node4.lchild = &node5;
    node4.rchild = &node8;
    node5.lchild = &node6;
    node5.rchild = &node7;
    int n = 0;
    n = lca(&node0,6,8);
    cout<<"节点6和节点8的最近公共祖先是"<<n<<endl;
    n = lca(&node0,2,5);
    cout<<"节点2和节点5的最近公共祖先是"<<n<<endl;
    n = lca(&node0,4,7);
    cout<<"节点4和节点7的最近公共祖先是"<<n<<endl;
}

输出

中序遍历:
2 1 3 0 6 5 7 4 8
节点对应层级:
2 1 2 0 3 2 3 1 2
节点6和节点8的最近公共祖先是4
中序遍历:
2 1 3 0 6 5 7 4 8
节点对应层级:
2 1 2 0 3 2 3 1 2
节点2和节点5的最近公共祖先是0
中序遍历:
2 1 3 0 6 5 7 4 8
节点对应层级:
2 1 2 0 3 2 3 1 2
节点4和节点7的最近公共祖先是4

PS

2012年写的练习小程序


如果我的文章对你有帮助,你可以给我打赏以促使我拿出更多的时间和精力来分享我的经验和思考总结。

微信支付码

发表评论

电子邮件地址不会被公开。

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据