C++_recursive_with brief analysis


  • 3
    • Thanks https://discuss.leetcode.com/topic/18561/4-lines-c-java-python-ruby

    • We consider a simplified case: 3 nodes : root, left, right:

    • Let's consider that if the root is NULL or root == p or root==q, we should return the root;

    • If not, then we search q and p from left children and right children. If we cannot find p and q, then that path will return NULL, which means that that p and q must be in the same side, then we will return the result of the other path.

    • If both path is not equal to NULL, then it means that the two nodes are in different path, we directly return the root node.

    • So from above analysis, we can divide this problem to smaller problems.

    class Solution {
    public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == NULL || root == p || root == q) return root;
        TreeNode* tmp1 = lowestCommonAncestor(root->left, p, q);
        TreeNode* tmp2 = lowestCommonAncestor(root->right, p, q);
        if(tmp1 == NULL){
            return tmp2;
        }else if(tmp2 == NULL){
            return tmp1;
        }
        return root;
    }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.