[RainbowSecret] C++ solution


  • 5

    Refering the post from G4G, we can know that we can construct path from root to p and q seperately.

    And compare the path TreeNode one by one.

    Also, a better solution is to find the p and q , return the parent node of the p and q recusively.

    So , in the final, we check whether they appear in the same tree or different tree.

    class Solution {
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            if(!root || root==p || root==q)  return root;
            TreeNode* left = lowestCommonAncestor(root->left, p, q);
            TreeNode* right=lowestCommonAncestor(root->right, p, q);
            
            /** find the LCA lowest parent **/
            if(left && right)  return root;
            /** this ensures that the LCA is the lowest **/
            /** as we just pass the LCA result back-track **/
            if(!left)  return right;
            if(!right)  return left;
        }
    };

  • 0

Log in to reply
 

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