36ms C++ one pass solution with comment, O(1) space, beat 74.73%


  • 2
    C
    class Solution {
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            if (root == NULL || root == p || root== q) {
                return root;
            }
         
            TreeNode *left_lca  = lowestCommonAncestor(root->left, p, q);
            TreeNode *right_lca = lowestCommonAncestor(root->right, p, q);
         
            if (left_lca && right_lca) {
                return root;
            }
         
            return (left_lca != NULL)? left_lca: right_lca;
        }
    };
    

  • 0
    Y

    @chenfu.xie
    I have a question in terms of the "root == p" and "root == q". Admittedly, this answer is correct according to the test. But this judgement is very dubious since it's hard to imagine that the p and q pointer are right point to the tree node. It's more realistic to write( root->val == p->val) and (root->val == q->val)


Log in to reply
 

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