Share C++/C# 24ms recursive solution


  • 8
    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;
    }

  • 3
    K

    what happens if p or q is not part of the tree?


  • 0
    O

    Good question: it will return p or q because the solution assumes that both p and q are part of the tree.
    The following code handles the case where only p or q are present

      TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
          if (root == NULL)
            return NULL;
          TreeNode* result = LowestCommonAncestorHelper(root, p, q);
          if (result != p && result != q)
            return result;
          if (result == p && LowestCommonAncestorHelper(root, NULL, q) == q)
            return result ;
          if (result == q && LowestCommonAncestorHelper(root, NULL, p) == p)
            return result;
          return NULL;
        }
    
        TreeNode* LowestCommonAncestorHelper(TreeNode* root, TreeNode* p, TreeNode* q)
        {
          if (root == NULL)
            return NULL;
          if (root == p || root == q)
          {
            return root;
          }
          TreeNode* left = LowestCommonAncestorHelper(root->left, p, q);
          TreeNode* right = LowestCommonAncestorHelper(root->right, p, q);
          if (left != NULL && right != NULL)
            return root;
          return left ? left: right;
        }

Log in to reply
 

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