Short and clean C++ solution


  • 18
    M

    Want to share my solution.

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        
        if (!root || !p || !q) {
            return NULL;
        }
        
        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;
        }
        
        return l? l : r;
    }

  • 2
    X

    The solution is elegant and efficient, but can not deal with cases that one node in the tree and the other not.


  • 0
    M

    Thanks for pointing to that, you are right.


  • 0
    E

    Very concise!


  • 0
    R

    Could you explain a little bit about this algorithm? Especially the line "if (root == p || root == q)". Why do you use OR operator here?


  • 0
    W

    could u explain this
    if (l && r) {
    return root;
    }


  • 0
    O

    if l and r are both valid (not NULL), p and q are in this root's two subtrees, thus root is the LCA


  • 0
    S

    It can not handle the case [1, 1, NULL, 2, 3], when search 1, 2.

    The solution will return the root node, what the real LCA is the root->left.


  • 0
    S

    What is the correct result when p = 1; q = 2; while the tree is [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2]


  • 0
    M

    Yes, you are right! So, algo works just for binary tree with unique key values. And both keys have to be present in the tree, as mentioned in first comment. Such limitations =)


  • 0
    M

    Read previous comment above.


Log in to reply
 

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