算法设计------Lowest Commen Ancestor

发表于 | 分类于 ，

举个栗子

给定一个二叉树，找到两个节点NA， NB的最近公共祖先(LCA)。

方便理解、比如对于下图:

Binary Search Tree 的LCA

在二叉搜索树中，利用BST属性，我们可以在O（h）时间找到LCA，其中h是树的高度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* 查找n1和n2的公共祖先，该函数假定 n1、n2存在于Binary Search Tree上*/
pLCA_Node lca(pLCA_Node root, int n1, int n2)
{
    while (root != NULL)
    {
        // 如果n1 ,n2都比根小，LCA存在于左子树
        if (root->member > n1 && root->member > n2)
            root = root->left_Child;
        
        // 如果n1 ,n2都比根小，LCA存在于右子树
        else if (root->member < n1 && root->member < n2)
            root = root->right_Child;
        
        else break;
    }
    return root;
}

普通二叉树的LCA

普通二叉树节点无特殊规律，无法按上述逻辑实现，对于普通二叉树NA、NB的公共祖先可分为以下三种情况（假定NA、NB存在于二叉树）：

  • 给定键NA或NB与root匹配，则root为LCA
  • NA、NB 分别在root的两边，LCA为root
  • NA、NB均位于左子树（或右子树），则LCA位于左子树（或右子树）

通过单次遍历二叉树查找LCA，时间复杂度为O（n）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
pLCA_Node findLCA(pLCA_Node root , int mem1, int mem2){
    if (root == NULL) {
        return NULL;
    }

    //如果mem1 或 mem2 与root 匹配，则根为LCA
    if (root -> member == mem1 || root -> member == mem2) {
        return root;
    }

    // 在左子树、右子树查找最近公共祖先
    pLCA_Node left_lca = findLCA(root -> left_Child, mem1, mem2);
    pLCA_Node right_lca = findLCA(root -> right_Child, mem1, mem2);

    //mem1、mem2 分别在root的两边，LCA为root
    if (left_lca && right_lca) {
        return root;
    }

    // LCA位于左子树或右子树
    return left_lca ? left_lca : right_lca;
}

上述实现是建立在NA、NB均存在于二叉树。如果NA、NB中某个值不存在于二叉树会将另一个值作为LCA返回（理想情况下应该返回NSNULL）。我们可以通过传递两个布尔变量v1、v2 来扩展这个这类情况，当树中存在n1时，v1置位true，当树中存在n2时，v2置为true。

完整实现

.h 文件

1
2
3
4
5
6
7
8
9
10
#include <stdio.h>

typedef struct lca_Node{
    struct lca_Node * left_Child;
    struct lca_Node * right_Child;
    int member;
}LCA_Node, * pLCA_Node;

pLCA_Node findLCA(pLCA_Node root , int mem1, int mem2);
pLCA_Node newLcaNode(int member);

.m 文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include "FindLCA.h"
#include "stdlib.h"
#include "stdbool.h"

pLCA_Node newLcaNode(int member){
    pLCA_Node temp = malloc(sizeof(LCA_Node));
    temp -> member = member;
    temp -> left_Child = temp -> right_Child = NULL;
    return temp;
}

pLCA_Node findLCAUtil(pLCA_Node root , int mem1, int mem2, bool * v1, bool * v2){
    if (root == NULL) {
        return NULL;
    }
    
    if (root -> member == mem1) {
        *v1 = true;
        return root;
    }
    if (root -> member == mem2) {
        *v2 = true;
        return root;
    }
    
    pLCA_Node left_lca = findLCAUtil(root -> left_Child, mem1, mem2, v1, v2);
    pLCA_Node right_lca = findLCAUtil(root -> right_Child, mem1, mem2, v1, v2);
    if (left_lca && right_lca) {
        return root;
    }
    return left_lca ? left_lca : right_lca;
}

bool findKey(pLCA_Node root, int key){
    if (root == NULL) {
        return false;
    }
    
    if (root -> member == key || findKey(root -> left_Child, key) || findKey(root -> right_Child, key)) {
        return true;
    }
    return false;
}

pLCA_Node findLCA(pLCA_Node root , int mem1, int mem2){
    
    bool v1 = false, v2 = false;
    
    pLCA_Node lca = findLCAUtil(root, mem1, mem2, &v1, &v2);
    
    if ((v1 && v2) || (v1 && findKey(root, mem2)) || (v2 && findKey(root, mem1))) {
        return lca;
    }
    
    return NULL;
}

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

void testFindLCA(){
//  构造一个上图所示的树
    pLCA_Node root = newLcaNode(1);
    root -> left_Child = newLcaNode(2);
    root -> right_Child = newLcaNode(3);
    root -> left_Child -> left_Child = newLcaNode(4);
    root -> left_Child -> right_Child = newLcaNode(5);
    root -> right_Child -> left_Child = newLcaNode(6);
    root -> right_Child -> right_Child = newLcaNode(7);
    
    pLCA_Node lca = findLCA(root, 4, 5);
    
    if (lca) {
        printf("LCA(4,5)---%d\n",lca -> member);
    }else{
        printf("Keys are not present");
    }
    
    lca = findLCA(root, 4, 10);
    
    if (lca) {
        printf("LCA(4,10)---%d\n",lca -> member);
    }else{
        printf("Keys are not present");
    }
}

执行结果

1
2
LCA(4,5)---2
Keys are not present

如果对你有帮助的话，Star✨下一吧！