235_LowestCommonAncestorofaBinarySearchTree - a920604a/leetcode GitHub Wiki

title: 235. Lowest Common Ancestor of a Binary Search Tree tags:
- backtracking categories: leetcode comments: false

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

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特性
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 節點

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

footer

⚠️ **GitHub.com Fallback** ⚠️