By

文章目录

/*在二叉樹中找到給定兩個節點的最低公共祖先 lowest common ancestor LCA
我們做一個規定：如果a是b的祖先，那麼他倆的LCA是a

*/

#include <iostream>
#include<list>
#include<vector>
using namespace std;

struct Node
{
    struct Node *left, *right;
    int key;
};

Node* newNode(int key)
{
    Node *temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return temp;
}
//************************方法一遞歸************************

/* 只用一次遍历解决LCA
學號二叉樹，用好遞歸
從root開始遍歷，如果n1,n2有一個與root匹配，那麼root就是LCA。如果都不匹配，遞歸左右子樹，如果
有一個在左子樹，一個在右子樹，那麼root是LCA。如果兩個數都在左子樹，則說明LCA在左子樹，否則在右子樹
*/

// 返回n1和n2的 LCA的指针
// 假设n1和n2都出现在树中
struct Node *findLCA1(struct Node* root, int n1, int n2)
{
    if (root == NULL) return NULL;

    // 只要n1 或 n2 的任一个匹配即可
    //  (注意：如果 一个节点是另一个祖先，则返回的是祖先节点。因为递归是要返回到祖先的 )
    if (root->key == n1 || root->key == n2)
        return root;
    // 分别在左右子树查找
    Node *left_lca  = findLCA1(root->left, n1, n2);
    Node *right_lca = findLCA1(root->right, n1, n2);
    // 如果都返回非空指针 Non-NULL, 则说明两个节点分别出现了在两个子树中，则当前节点肯定为LCA
    if (left_lca && right_lca)  return root;
    // 如果一个为空，在说明LCA在另一个子树
    return (left_lca != NULL)? left_lca: right_lca;
}

//************************方法二找到路徑，求路徑的最後一個公共節點****************
//找到給定節點的路徑
bool GetNodePath(Node* pRoot,int key, list<Node*>&path){
    if(pRoot==NULL)
        return false;
    path.push_back(pRoot);//關鍵在於存放節點與判斷的順序
    if(pRoot->key==key)
        return true;


    //左右子樹是否找到，找到的話，當前節點就在路徑中
    bool found=(GetNodePath(pRoot->left,key,path) ||GetNodePath(pRoot->right,key,path));
    if(!found)//沒有找到就彈出
         path.pop_back();
    return found;

}
//查看路徑上的節點
void PrintPath(list<Node*>&path){
    Node* pLast=NULL;
    list<Node*>::const_iterator iter1=path.begin();
    while(iter1!=path.end()){

        pLast=*iter1;
        cout<<pLast->key<<" ";
        iter1++;
    }
    cout<<endl;
}
//得到兩條路上的最後一個公共節點
Node* GetLastCommonNode(const list<Node*>& path1,const list<Node*>& path2){
    list<Node*>::const_iterator iter1=path1.begin();
    list<Node*>::const_iterator iter2=path2.begin();
    Node* pLast=NULL;

    while(iter1!=path1.end() && iter2!=path2.end()){
        if(*iter1==*iter2)
            pLast=*iter1;
        iter1++;
        iter2++;
    }
    return pLast;
}
//找到兩個指點節點的最低公共祖先（根節點的祖先是他自己）
Node* findLCA2(Node* pRoot, int key1,int key2){
    list<Node*> path1;
    list<Node*> path2;
    if(pRoot==NULL )//輸入無效，找不到
    {

        return NULL;
    }

    if(GetNodePath(pRoot,key1,path1) &&  GetNodePath(pRoot,key2,path2))
            return GetLastCommonNode(path1,path2);


}

//测试
int main()
{
    // 构造上面图中的树
    Node * root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
//    cout << "LCA(4, 5) = " << findLCA1(root, 4, 5)->key;
//    cout << "\nLCA(4, 6) = " << findLCA1(root, 4, 6)->key;
//    cout << "\nLCA(3, 4) = " << findLCA1(root, 3, 4)->key;
//    cout << "\nLCA(2, 4) = " << findLCA1(root, 2, 4)->key;

  // cout<<endl;


    Node* p1=NULL;Node* p2=NULL;

    p1= findLCA1(root,6,7);
    p2= findLCA2(root,6,7);
    cout<<"last node1:"<<p1->key<<endl;
    cout<<"last node2:"<<p2->key<<endl;
    return 0;
}
文章目录