[jobdu]树中两个结点的最低公共祖先

http://ac.jobdu.com/problem.php?pid=1509

此题最直观的方法是两次DFS，分别找到这两个节点的path，然后遍历path1和path2做比较，找到最后一个共同的元素。这个普通的做法在：http://blog.csdn.net/thyftguhfyguj/article/details/9232901

但有个更好的办法能够一次DFS中找到，没有O(logN)的额外空间。参见：http://www.cnblogs.com/lyunyu/archive/2013/05/11/3073529.html

现在这段代码有一个用例没有过，应该是没有同时找到两个节点（比如只找到一个）。这样可以放两个是否找到a和b的bool，最后有用，但这样代码会复杂不少。过会再做。（http://www.cnblogs.com/remlostime/archive/2012/11/26/2788795.html）现在这段代码只适用于两个子节点都有的情况。

但事实上LCA是一个成熟的算法，参考：http://wenku.baidu.com/view/6918633343323968011c92f4.html 有空回来再研究（看了一下，那个好像是基于并查集的离线算法）。

如果是二叉排序树，则可利用左右大小的性质：http://www.cnblogs.com/lautsie/p/3269174.html

#include <cstdio>

#include <iostream>

using namespace std;

struct Node{

    int x;

    struct Node *left;

    struct Node *right;

};

void createTree(Node *&root){

     int x;

     scanf_s("%d",&x);

     if(!x)

        root = NULL;

     else{

        root = new Node;

        root->x = x;

        createTree(root->left);

        createTree(root->right);

     }

}

Node* getCommonNode(Node *&root, int a, int b){

    if (root == NULL) {

        return NULL;

    }

    else if (root->x == a || root->x == b){

        return root;

    }

    else {

        Node* rl = getCommonNode(root->left, a, b);

        Node* rr = getCommonNode(root->right, a, b);

        if (rl != NULL && rr != NULL) return root;

        else {

            Node* res = (rl != NULL) ? rl : rr;

            return res;

        }

    }

}

void destory(Node *&root){

    if(root){

        destory(root->left);

        destory(root->right);

        delete root;

        root = NULL;

    }

}

void print(Node *root){

    if(root){

        printf("%d ",root->x);

        print(root->left);

        print(root->right);

    }

}

int main()

{

    int n,a,b;

    while(scanf_s("%d",&n) != EOF){

        while(n--){

            Node *root;

            createTree(root);

            scanf_s("%d %d",&a,&b);

            Node * res = getCommonNode(root, a, b);

            if (res != NULL) {

                printf("%d\n", res->x);

            }

            else {

                printf("My God\n");

            }

            destory(root);

        }

    }

    return 0;

}

巴特西

[jobdu]树中两个结点的最低公共祖先

最新文章

热门文章