C++ 12ms concise recursion considering not both p and q exist (return NULL)


  • 0
    Z

    Using 2 bool variables f1, f2 to indicate the existence of p and q

    class Solution {
    public:
        TreeNode *helper(TreeNode *root, TreeNode *p, TreeNode *q, bool &f1, bool &f2) {
            if (!root) return NULL;
            else if (root == p) {
                f1 = true;
                return root;
            } else if (root == q) {
                f2 = true;
                return root;
            }
            TreeNode *left = helper(root->left, p, q, f1, f2);
            TreeNode *right = helper(root->right, p, q, f1, f2);
            if (!left && !right) return NULL;
            else if (left && right) return root;
            else return left ? left : right;
        }
        
        bool findNode(TreeNode *root, TreeNode *target) {
            if (!root) return false;
            if (root == target) return true;
            return findNode(root->left, target) || findNode(root->right, target);
        }
        
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            if (!root || !p || !q) return NULL;
            bool f1 = false, f2 = false;
            TreeNode *tmp = helper(root, p, q, f1, f2);
            if (!tmp) return NULL;
            if (f1 && !f2 && !findNode(tmp, q)) return NULL;
            if (f2 && !f1 && !findNode(tmp, p)) return NULL;
            return tmp;
        }
    };
    

Log in to reply
 

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