查找二叉树的最近公共祖先

版权声明 本站原创文章 由 萌叔 发表
转载请注明 萌叔 | https://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年写的练习小程序

请我喝瓶饮料