235. Lowest Common Ancestor of a Binary Search Tree

發表於 | 分類於

problem

Follow up 236. Lowest Common Ancestor of a Binary Tree

solution

  • 比較root p q 三個節點的值
  • 如果root->val 是其他兩個節點的值，則return root
  • 如果root->val 小於其他兩節點的值，則向root->right 搜尋
  • 如果root->val 大於其他兩節點的值，則向root->left 搜尋
  • 剩餘狀況，則return root

option 1 - recursive

1
2
3
4
5
6
7
8
9
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == p || root == q) return root;
        if(root->val > min(p->val, q->val) && root->val < max(p->val, q->val)) return root;
        else if(root->val < p->val && root->val < q->val) return lowestCommonAncestor(root->right, p, q);
        return lowestCommonAncestor(root->left,p, q);   
    }
};

if(root->val > p->val && root->val > q->val) 可改成
if(root->val > max(p->val, q->val) )

  • postorder
    沒用到BST特性
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    class Solution {
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            if(!root) return root;
            if(root ==p || root==q) return root;
            TreeNode *l = lowestCommonAncestor(root->left, p, q);
            TreeNode *r = lowestCommonAncestor(root->right, p, q);
            
            if( l && r) return root;
            else if(!l) return r;
            return l;
        }
    };

    option 2 - iterative

    不斷更新root 節點
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        while(root){
            if(root ==p || root==q) return root;
            else if(root->val > p->val && root->val > q->val) root = root->left;
            else if(root->val < p->val && root->val < q->val) root = root->right;
            else return root;
        }
        return nullptr;
    }
};

analysis

  • time complexity O(n) n is node number of tree
  • space complexity O(h) h is height of tree