236. Lowest Common Ancestor of a Binary Tree

發表於 | 分類於

problem

solution

option 1
  • 先遞迴檢查 p和q 是否在root的左子樹
  • 如果都在左子樹，則往左子樹搜尋
  • 如果都不在，則往右子樹搜尋
  • 其餘狀況，則return root
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool cover(TreeNode * node, TreeNode * p){
        if(!node) return false;
        if(node==p) return true;
        return cover(node->left, p) || cover(node->right,p); 
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==p || root==q) return root;
        bool pchild = cover(root->left, p);
        bool qchild = cover(root->left, q);
        if(pchild && qchild) return lowestCommonAncestor(root->left, p, q);
        else if(!pchild && !qchild) return lowestCommonAncestor(root->right, p, q);
        return root;      
    }
};

option 2 - dfs + postorder traverse

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;
        // post-order
        TreeNode *left = lowestCommonAncestor(root->left, p, q);
        TreeNode *right = lowestCommonAncestor(root->right, p, q);
        if(left && right) return root;
        return left==nullptr?right:left;
    }
};

analysis

  • option 1
    • time complexity O(t) t is the size of the subtree for the first common ancestor on average case, O(n) on worst case, n is number of nodes in BT
    • space complexity O(h)
  • option 2
    • time complexity O(n) n is number of nodes in BT
    • space complexity O(h) h is the height of BT