C++ code with clear explanaton


  • 0
    C
    class Solution {
    public:
    
        // only when root is in the middle of p and q, root is the LCA
        
        // LCA_BinaryTree(root, p, q) = 
        // if root=p. p
        // if root=q. q
        // if root=NULL, NULL
        // if LCA_BinaryTree(root->left, p, q) && LCA_BinaryTree(root->right, p, q). root
        // if LCA_BinaryTree(root->left, p, q)=NULL. LCA_BinaryTree(root->right, p, q)
        // if LCA_BinaryTree(root->right, p, q)=NULL. LCA_BinaryTree(root->left, p, q)
        
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
        {
            if(!p) q;
            if(!q) p;
            
            if(!root || 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;
            if(!l) return r;
            if(!r) return l;
        }
    };

Log in to reply
 

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