Handling case of duplicates.


  • 0
    H
    class Solution {
    public:
        TreeNode *DFS(TreeNode *root, TreeNode *p) {
            if (root == nullptr) {
                return nullptr;
            }
            if (root == p) {
                if (root->right == nullptr) {
                    // case 1: no right subtree.
                    return root;
                } else {
                    // case 2: right subtree exists!
                    auto successor = root->right;
                    while (successor->left) {
                        successor = successor->left;
                    }
                    return successor;
                }
            }
            
            // search left.
            auto left = DFS(root->left, p);
            if (left && left != p) {
                return left;
            }
            if (left == p) {
                return root;
            }
            // search right.
            return DFS(root->right, p);
        }
    
        TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
            auto node = DFS(root, p);
            return node != p? node : nullptr;
        }
    };

  • 0

    I don't understand because p is a pointer then why duplications exist.


Log in to reply
 

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