48. 二叉树两结点的最低共同父结点(3种变种情况)[Get lowest common ancestor of binary tree]

时间：2020-12-05 07:50:11

【题目】

输入二叉树中的两个结点，输出这两个结点在数中最低的共同父结点。

二叉树的结点定义如下：

 C++ Code 
1
2
3
4
5
6
  
struct BinaryTreeNode
{
    int value;
    BinaryTreeNode *left;
    BinaryTreeNode *right;
};

【分析】

求数中两个结点的最低共同结点是面试中经常出现的一个问题。这个问题有几个变种。

【变种1】

第一个变种是二叉树是一种特殊的二叉树：查找二叉树。也就是树是排序过的，位于左子树上的结点都比父结点小，而位于右子树的结点都比父结点大。我们只需要从根结点开始和两个结点进行比较。如果当前结点的值比两个结点都大，则最低的共同父结点一定在当前结点的左子树中。如果当前结点的值比两个结点都小，则最低的共同父结点一定在当前结点的右子树中。

具体代码如下：

 C++ Code 
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
  
// 48_GetLowestCommonAncessor.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

struct BinaryTreeNode
{
    int value;
    BinaryTreeNode *left;
    BinaryTreeNode *right;
};

BinaryTreeNode* create_tree_r(int a[],int left,int right)
{
    // base case for leaf-node
    if (left>right)
        return NULL;
    ;
    BinaryTreeNode *root = new BinaryTreeNode();
    root->value = a[mid];
    if(left<=mid)
        root->left = create_tree_r(a,left,mid-);
    if (right>=mid)
        root->right = create_tree_r(a,mid+,right);
    return root;
}

BinaryTreeNode* CreateTree(int a[],int length)
{
    )
        return NULL;
    );
}

// whether tree root has node x?
bool HasNode(BinaryTreeNode *root,int x)
{
    if(NULL==root)
        return false;
    if (root->value==x)
    {
        return true;
    }
    else if (root->value<x)
    {
        return HasNode(root->right,x);
    }
    else 
    {
        return HasNode(root->left,x);
    }
}

// check whether root tree has node
bool HasNode(BinaryTreeNode *root,BinaryTreeNode *node)
{
    if (root==node)
        return true;
    bool bLeft = false;
    bool bRight = false;
    // check in left sub-tree
    if (root->left!=NULL)
        bLeft = HasNode(root->left,node);

// check in left right-tree
    if (root->right!=NULL)
        bRight = HasNode(root->right,node);
    return bLeft||bRight;
}

// get lowest common ancestor recursively
BinaryTreeNode* GetLowestCommonAncestor_Recursively(BinaryTreeNode *root,int x,int y)
{
    if(NULL==root)
        return NULL;
    if(root->value>=x && root->value<=y)
    {// x in left and y in right sub-tree
        return root;
    }
    else if (root->value<x)
    {// x y in right sub-tree
        return GetLowestCommonAncestor_Recursively(root->right,x,y);
    }
    else
    //else if(root->value>y)
    {// x y in left sub-tree 
        return GetLowestCommonAncestor_Recursively(root->left,x,y);
    }
}

// get lowest common ancestor iteratively
BinaryTreeNode* GetLowestCommonAncestor_Iteratively(BinaryTreeNode *root,int x, int y)
{
    if(NULL==root)
        return NULL;
    BinaryTreeNode *cur = root;
    while(cur!=NULL)
    {
        if(cur->value>=x && cur->value<=y)
        {// x in left and y in right sub-tree
            return cur;
        }
        else if (cur->value<x)
        {// x y in right sub-tree
            cur = cur->right;
        }
        else 
        {// x y in left sub-tree 
            cur = cur->left;
        }
    }
    return cur;
}

// get lca for x and y 
BinaryTreeNode* GetLCA_Solution(BinaryTreeNode *root,int x,int y)
{
    // check whether root has x and y
    if (HasNode(root,x)&&HasNode(root,y))
        return GetLowestCommonAncestor_Iteratively(root,x,y);
    else 
        return NULL;
}

void test_base(BinaryTreeNode *root,int x,int y)
{
    BinaryTreeNode *result = GetLCA_Solution(root,x,y);
    if (NULL==result)
    {
        printf("%s\n","can not find lca.");
    }
    else
    {
        printf("%d,%d--->%d\n",x,y,result->value);
    }
}

void test_case()
{
    /*
                 5
                /\
               /  \
              /    \
             2     7
            / \   / \
           /  |   |  \
          1   3  6  8
                \        \
                4         9
    */
    };
    int length = sizeof(a)/sizeof(int);
    BinaryTreeNode *root = CreateTree(a,length);
    test_base(root,); // 5
); // 2
); // 7
    // special case
); // cannot find lca
);// cannot find lca
}

int _tmain(int argc, _TCHAR* argv[])
{
    test_case();
    ;
}
/*
4,9--->5
1,4--->2
6,9--->7
can not find lca.
can not find lca.
*/

【变种2】

第二个变种是树为多叉树，每个结点都有一个指针指向它的父结点。于是我们可以从任何一个结点出发，得到一个到达树根结点的单向链表。因此这个问题转换为两个单向链表的第一个公共结点，之前35.两链表的第一个公共结点已经讨论过。

【变种3】

第三个变种是树为多叉树，每个父节点有若干个子节点，但是子节点没有指向父节点指针。我们只能从根节点遍历树，从而得到从根节点到某一节点的路径，然后求这两个路径的最后一个公共节点。

本题中的二叉树是第三个变种的一个特例，即每个父节点只有左右子节点。

具体代码如下：

 C++ Code 
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
57
58
59
60
  
#include <vector>
#include <iostream>
using namespace std;

// treenode
struct TreeNode
{
    int value;
    vector<TreeNode*> vChildren;
};

// get tree node path from root to node
bool GetNodePath(TreeNode *root,TreeNode *node,vector<TreeNode*> &path)
{
    if(root==node)
        return true;
    path.push_back(root);
    // find node in root's children
    bool found = false;
    vector<TreeNode*>::iterator iter = root->vChildren.begin();
    while(!found&&iter<root->vChildren.end())
    {
        found = GetNodePath(*iter,node,path);
        iter++;
    }
    // if not found in root's children,then remove it from path
    if (!found)
        path.pop_back();
    return found;
}

// get last common node of path1 and path2
TreeNode* GetLastCommonNode(const vector<TreeNode*> &path1,const vector<TreeNode*> &path2)
{// A-B-D, A-B-E
    vector<TreeNode*>::const_iterator iter1= path1.begin();
    vector<TreeNode*>::const_iterator iter2= path2.begin();

TreeNode *lastNode = NULL;
    while(iter1!=path1.end()&&iter2!=path2.end())
    {
        if (*iter1==*iter2)
            lastNode = *iter1;
        iter1++;
        iter2++;
    }
    return lastNode;
}

// get lowest common ancestor 
TreeNode* GetLCA(TreeNode* root,TreeNode *node1,TreeNode *node2)
{// O(n)+O(n)+O(n) = O(n)
    if(NULL==root||NULL==node1||node2==NULL)
        return NULL;
    vector<TreeNode*> path1;
    GetNodePath(root,node1,path1);
    vector<TreeNode*> path2;
    GetNodePath(root,node2,path2);
    return GetLastCommonNode(path1,path2);
}

【参考】

http://zhedahht.blog.163.com/blog/static/25411174201081263815813/

http://blog.csdn.net/dahai_881222/article/details/7801356

http://www.cnblogs.com/venow/archive/2012/08/31/2664969.html

【本文链接】

http://www.cnblogs.com/hellogiser/p/get-lowest-common-ancestor-of-binary-tree.html

相关文章