2016年2月6日 星期六

LEET code --Lowest Common Ancestor of a Binary Search Tree

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

張貼者： 於
標籤：

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)