Share 40ms C++/C# recursive solution


  • 1
    O

    C++ version

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            if(!root)
                return NULL;
            if(root == p || root == q)
                return root;
            // Check if left contains p or q
            TreeNode* left = lowestCommonAncestor(root->left, p, q);
            // Check if right contains p or q
            TreeNode* right = lowestCommonAncestor(root->right, p, q);
            // if left and right containsp or q the it'sthe LCA
            if(left && right)
                return root;
            return left ? left : right;        
        }
    

    C# version

    public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null)
            return null;
        if(root == p || root == q)
            return root;
        var left = LowestCommonAncestor(root.left, p, q);
        var right = LowestCommonAncestor(root.right, p, q);
        if(left != null && right != null)
            return root;
        return left ?? right;
    }

  • 0
    E

    @ohini Can you explain why did you have to return left or right in your last statement?


Log in to reply
 

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