LCA(Lowest Common Ancestor)笔记(一)

LCA(Lowest Common Ancestor)笔记(一)

二叉搜索树(Binary Searching Tree)情形:

O(h)的方案,根据LCA的性质我们可以推测出,对于每一个结点,所要寻找的LCA结点一定是一下四种之一:

1. 当前结点本身

2.当前结点的左子树里

3.当前结点的右子树里

4.不存在这样的LCA(当且仅当输入的两个结点至少一个不存在于这棵树中)

对于二叉搜索树(Binary Searching Tree),两个结点分别在当前结点两侧(即一个结点小于等于当前结点,另一个结点大于等于当前结点)时,LCA恰好就是当前结点本身。当两个结点都小于当前结点,则根据BST的性质,可以知道LCA在当前结点的左子树中,反之在右子树中,如果深入到了叶子结点还没有找到,则说明这棵树中不存在当前结点。

递归实现:

#include <iostream>

using namespace std;

struct Node {
    int val;
    Node *left, *right;
    Node(int v = 0) : val(v) {
        left = right = nullptr;
    }
};

Node * lca(Node *root, int n1, int n2) {
    if (!root) return NULL;
    if (n1 < root->val && n2 < root->val)
        return lca(root->left, n1, n2);
    else if (n1 > root->val && n2 > root->val)
        return lca(root->right, n1, n2);
    else
        return root;
}

void delTree(Node *root) {
    if (!root) return;
    delTree(root->left);
    delTree(root->right);
    delete root;
}

int main(void) {
    // init the tree
    Node *root = new Node(20);
    root->left = new Node(8);
    root->right = new Node(22);
    root->left->left = new Node(4);
    root->left->right = new Node(12);
    root->left->right->left = new Node(10);
    root->left->right->right = new Node(14);

    // get LCA
    int n1 = 10, n2 = 14;
    Node *t = lca(root, n1, n2);
    printf("LCA of %d and %d is %d \n", n1, n2, t->val);

    n1 = 14, n2 = 8;
    t = lca(root, n1, n2);
    printf("LCA of %d and %d is %d \n", n1, n2, t->val);

    n1 = 10, n2 = 22;
    t = lca(root, n1, n2);
    printf("LCA of %d and %d is %d \n", n1, n2, t->val);

    // destroy tree
    delTree(root);

    return 0;
}

递推实现:

#include <iostream>

using namespace std;

struct Node {
    int val;
    Node *left, *right;
    Node(int v = 0) : val(v) {
        left = right = nullptr;
    }
};

Node * lca(Node *root, int n1, int n2) {
    while (root) {
        if (n1 < root->val && n2 < root->val)
            root = root->left;
        else if (n1 > root->val && n2 > root->val)
            root = root->right;
        else
            break;
    }
    return root;
}

void delTree(Node *root) {
    if (!root) return;
    delTree(root->left);
    delTree(root->right);
    delete root;
}

int main(void) {
    // init the tree
    Node *root = new Node(20);
    root->left = new Node(8);
    root->right = new Node(22);
    root->left->left = new Node(4);
    root->left->right = new Node(12);
    root->left->right->left = new Node(10);
    root->left->right->right = new Node(14);

    // get LCA
    int n1 = 10, n2 = 14;
    Node *t = lca(root, n1, n2);
    printf("LCA of %d and %d is %d \n", n1, n2, t->val);

    n1 = 14, n2 = 8;
    t = lca(root, n1, n2);
    printf("LCA of %d and %d is %d \n", n1, n2, t->val);

    n1 = 10, n2 = 22;
    t = lca(root, n1, n2);
    printf("LCA of %d and %d is %d \n", n1, n2, t->val);

    // destroy tree
    delTree(root);

    return 0;
}

 

对于更为一般的二叉树,我们的策略如下:

第一种,利用从根结点到两个目标结点的路径。利用这一性质的方案,大都具有O(h)复杂度,有些还需要额外存储空间。

(1)我们可以先走两次路径,分别是从根节点深搜到结点1,以及从根节点深搜到结点2,将两个路径记录到两个数组中,之后从这两个数组最开始的位置同时往后查,直到找到第一个不一样的点,这说明,在从根到两个结点的路径上,从这个结点开始以及之后的所有结点都不相同,而前面路径上的结点都相同,那么LCA就是这样第一个不相同的这组结点之前的一个结点。

(2)我们可以记录parent的位置,由于每个结点有一个独特的存储位置(如果是动态分配存储,这个位置就是地址,而如果使用静态数组进行存储,这个位置就是数组序号了),那么我们可以从第一个结点倒推会根节点,使用STL的map建立一个从结点存储位置值到表示该结点是否存在于路径中的布尔变量的一个映射(相当于一个Hash 表),利用这个,我们再从第二个结点倒推回根节点,路径上每个结点都尝试判断它是否被加入到了map中,找到的第一个存在于map中的结点,它便是LCA,使用set可以达到同样的效果。

代码:

#include <iostream>
#include <map>
#include <vector>

using namespace std;

struct Node {
    int val;
    Node *left, *right, *parent;
    Node(int v = 0, Node *p = nullptr) : val(v), parent(p) {
        left = right = nullptr;
    }
};

Node *lca(Node *n1, Node *n2) {
    map<Node *, bool> vis;
    while (n1) {
        vis[n1] = true;
        n1 = n1->parent;
    }
    while (n2) {
        if (vis[n2]) return n2;
        n2 = n2->parent;
    }
    return nullptr;
}

void delTree(Node *root) {
    if (!root) return;
    delTree(root->left);
    delTree(root->right);
    delete root;
}

int main(void) {
    // init the tree
    Node *root = new Node(1);
    root->left = new Node(2, root);
    root->right = new Node(3, root);
    root->left->left = new Node(4, root->left);
    root->left->right = new Node(5, root->left);
    root->right->left = new Node(6, root->right);
    root->right->right = new Node(7, root->right);

    // get LCA
    Node *n1 = root->left->left, *n2 = root->left->right;
    Node *ans;
    printf("LCA of %d and %d is %d\n", n1 ? n1->val : -1, n2 ? n2->val : -1, (ans = lca(n1, n2)) ? ans->val : -1);

    n1 = root->right->left, n2 = root->left->right;
    ans = NULL;
    printf("LCA of %d and %d is %d\n", n1 ? n1->val : -1, n2 ? n2->val : -1, (ans = lca(n1, n2)) ? ans->val : -1);

    n1 = nullptr, n2 = nullptr;
    ans = NULL;
    printf("LCA of %d and %d is %d\n", n1 ? n1->val : -1, n2 ? n2->val : -1, (ans = lca(n1, n2)) ? ans->val : -1);

    n1 = root->left, n2 = root->left->right;
    ans = NULL;
    printf("LCA of %d and %d is %d\n", n1 ? n1->val : -1, n2 ? n2->val : -1, (ans = lca(n1, n2)) ? ans->val : -1);

    n1 = root, n2 = root->left->left;
    ans = NULL;
    printf("LCA of %d and %d is %d\n", n1->val, n2->val, (ans = lca(n1, n2)) ? ans->val : -1);

    // destroy tree
    delTree(root);

    return 0;
}

 

(3)我们甚至可以不需要使用map这样的额外存储,当存储有parent位置后,我们需要的仅仅是找到它们路径上第一个共同的点是哪个,遇到问题仅仅是,由于两个点深度不同,倒推回根节点的过程中,它们“路过”那个要找的LCA结点的“时间”可能不同,这个问题其实很好解决,我们只要让它们的深度预处理到相同的就可以,我们只要将较深的结点先向前推几层,这个层数取决于两个结点在树中的层数差值,之后两个结点同时倒推,遇到的第一个公共点就是LCA结点。

代码:

#include <iostream>
#include <map>
#include <vector>

using namespace std;

struct Node {
    int val;
    Node *left, *right, *parent;
    Node(int v = 0, Node *p = nullptr) : val(v), parent(p) {
        left = right = nullptr;
    }
};

int getDepth(Node *n) {
    int ret = -1;
    while (n) {
        ret++;
        n = n->parent;
    }
    return ret;
}

Node *lca(Node *n1, Node *n2) {
    int d1 = getDepth(n1), d2 = getDepth(n2);
    if (d1 < 0 || d2 < 0) return nullptr;
    int diff = d1 - d2;
    if (diff < 0) {
        diff = -diff;
        Node *tmp = n1;
        n1 = n2;
        n2 = tmp;
    }
    while (diff--) n1 = n1->parent;
    while (n1 && n2) {
        if (n1 == n2) return n1;
        n1 = n1->parent, n2 = n2->parent;
    }
    return nullptr;
}

void delTree(Node *root) {
    if (!root) return;
    delTree(root->left);
    delTree(root->right);
    delete root;
}

int main(void) {
    // init the tree
    Node *root = new Node(1);
    root->left = new Node(2, root);
    root->right = new Node(3, root);
    root->left->left = new Node(4, root->left);
    root->left->right = new Node(5, root->left);
    root->right->left = new Node(6, root->right);
    root->right->right = new Node(7, root->right);

    // get LCA
    Node *n1 = root->left->left, *n2 = root->left->right;
    Node *ans;
    printf("LCA of %d and %d is %d\n", n1 ? n1->val : -1, n2 ? n2->val : -1, (ans = lca(n1, n2)) ? ans->val : -1);

    n1 = root->right->left, n2 = root->left->right;
    ans = NULL;
    printf("LCA of %d and %d is %d\n", n1 ? n1->val : -1, n2 ? n2->val : -1, (ans = lca(n1, n2)) ? ans->val : -1);

    n1 = nullptr, n2 = nullptr;
    ans = NULL;
    printf("LCA of %d and %d is %d\n", n1 ? n1->val : -1, n2 ? n2->val : -1, (ans = lca(n1, n2)) ? ans->val : -1);

    n1 = root->left, n2 = root->left->right;
    ans = NULL;
    printf("LCA of %d and %d is %d\n", n1 ? n1->val : -1, n2 ? n2->val : -1, (ans = lca(n1, n2)) ? ans->val : -1);

    n1 = root, n2 = root->left->left;
    ans = NULL;
    printf("LCA of %d and %d is %d\n", n1->val, n2->val, (ans = lca(n1, n2)) ? ans->val : -1);

    // destroy tree
    delTree(root);

    return 0;
}

 

第二种,和刚才BST中的解决策略类似,同样是考虑到上面所述的四种可能,只是我们不具有BST那样小的必然在左子树、大者必然在右子树那样的性质,于是我们需要遍历这棵树来解决,复杂度O(V)。

#include <iostream>
#include <vector>

using namespace std;

struct Node {
    int val;
    Node *left, *right;
    Node(int v = 0) : val(v) {
        left = right = nullptr;
    }
};

Node *lca(Node *root, int n1, int n2) {
    if (!root) return NULL;
    if (root->val == n1 || root->val == n2)
        return root;
    Node *left = lca(root->left, n1, n2);
    Node *right = lca(root->right, n1, n2);
    if (left && right) return root;
    return left ? left : right;
}

void delTree(Node *root) {
    if (!root) return;
    delTree(root->left);
    delTree(root->right);
    delete root;
}

int main(void) {
    // init the tree
    Node *root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);
    root->right->right = new Node(7);

    // get LCA
    int n1 = 4, n2 = 5;
    Node *ans;
    printf("LCA of %d and %d is %d\n", n1, n2, (ans = lca(root, n1, n2)) ? ans->val : -1);

    n1 = 6, n2 = 5;
    ans = NULL;
    printf("LCA of %d and %d is %d\n", n1, n2, (ans = lca(root, n1, n2)) ? ans->val : -1);

    n1 = 8, n2 = 9;
    ans = NULL;
    printf("LCA of %d and %d is %d\n", n1, n2, (ans = lca(root, n1, n2)) ? ans->val : -1);

    n1 = 2, n2 = 5;
    ans = NULL;
    printf("LCA of %d and %d is %d\n", n1, n2, (ans = lca(root, n1, n2)) ? ans->val : -1);

    n1 = 1, n2 = 4;
    ans = NULL;
    printf("LCA of %d and %d is %d\n", n1, n2, (ans = lca(root, n1, n2)) ? ans->val : -1);

    // destroy tree
    delTree(root);

    return 0;
}