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

1
2
3
4
5
6

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

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.
*/

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);
}