C++ dfs version, while p or q does not exist in tree, return nullptr

  • 3

    I had a previous version, which does not return nullptr while one of the nodes does not in the tree.

       TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        return LCAHelper(root, p, q).second;
    pair<int, TreeNode *> LCAHelper(TreeNode *root, TreeNode *p, TreeNode *q) {
        if (!root) return {0, nullptr};
        auto L = LCAHelper(root->left, p, q);
        if (L.first == 2) return L;
        auto R = LCAHelper(root->right, p, q);
        if (R.first == 2) return R;
        int total = L.first + R.first + (root == p || root == q);
        return {total, total == 2 ? root : nullptr};

Log in to reply

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