Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
According to the
definition of LCA on Wikipedia:
“The lowest common ancestor is defined between two nodes v and w as the
lowest node in T that has both v and w as descendants (where we allow
a node to be a descendant of itself).”
_______6______
/ \
___2__ ___8__
/ \ / \
0 _4 7 9
/ \
3 5
For example, the lowest common ancestor (LCA) of nodes
2 and
8 is
6. Another example is LCA of nodes
2 and
4 is
2, since a node can be a descendant of itself according to the LCA definition.
這題解法用兩個狀態來代表 如果-1 代表底下沒有目標
如果0代表有找到
如果都找到了 就把pointer記錄在ans
但是要注意 因為我要記錄的是 pointer的位置 所以必須要用double pointer
所以在30行的 *ans=root
就會把在11行的temp指向root裡面紀錄的記憶體位置
關於pointer的關係 可以看
http://wp.mlab.tw/?p=176
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
| /**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
struct TreeNode a;
struct TreeNode *temp=&a;
struct TreeNode** ans=&temp;//(struct TreeNode*)malloc(sizeof(struct TreeNode**));
parse(root,p,q,ans);
printf("ans=%d, root=%d",(*ans)->val,root->val);
return *ans;
}
int parse(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q, struct TreeNode** ans ){
int anscount=0;
if(root==NULL)return -1;
if(root->val ==p->val || root->val==q->val)anscount++;
//printf("root:%d p=%d q=%d, ans=%d ",root->val,p->val,q->val,anscount);
int le = parse(root->left,p,q,ans);
int re = parse(root->right,p,q,ans);
if(le==0 )anscount++;
if(re ==0)anscount++;
if(anscount>=2){
printf("ans=%d",(*ans)->val);
*ans=root;
printf("root=%d, ans=%d ",root->val,(*ans)->val);
return -1;
}else return anscount-1;
}
|
-------------
上面的太冗了
如果左邊有檢查到 但是右邊都沒有 那代表p q都集中在左邊
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| /**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
if(root==NULL)return NULL;
if(root == p || root==q)return root;
struct TreeNode* le=lowestCommonAncestor(root->left,p,q);
struct TreeNode* ri=lowestCommonAncestor(root->right,p,q);
if(le && ri)return root; //both of the le and ri have value==> lowest
if(le)return le;//only re have value
else return ri;//only ri have value
}
|
----------
因為是BST
所以 root的左邊都是小於root的
而LST 是找 q<=lst<=p
因此可以簡單的while跑完
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
| /**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
//because it is a bst ans assume p<=q
//so the lst must be p<=lst<=q
// therefore, is the current root<p -->the lst must be higher lst(root->right,p,q)
//root>q -->the lst must be lowwer lst(root->left,p,q)
if(p->val > q->val){
struct TreeNode* temp=q;
q=p;
p=temp;
}
struct TreeNode * lst=root;
while(true){
if( lst->val < p->val)lst=lst->right;
else if(lst->val > q->val)lst=lst->left;
else break;
}
return lst;
}
|
