Share my C++ solution using Morris traversal with O(1) space and O(n) time


  • 0
    M

    The following code does a complete Morris traversal since the OJ will give me runtime error if I return the successor immediately after finding it. The reason is Morris traversal will destruct the tree during traversal, so you need to do a complete Morris traversal to recover everything. In an interview, you should ask your interviewer whether you can modify the input before going with this method.

    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
            if (!p) return NULL;
            TreeNode *cur = root, *ret = NULL, *prev = NULL;
            while (cur) {
                if (cur->left) {
                    TreeNode *pre = cur->left;
                    while (pre->right && pre->right != cur) pre = pre->right;
                    if (pre->right != cur) {
                        pre->right = cur;
                        cur = cur->left;
                    } else {
                        pre->right = NULL;
                        if (prev == p) ret = cur;
                        prev = cur;
                        cur = cur->right;
                    }
                } else {
                    if (prev == p) ret = cur;
                    prev = cur;
                    cur = cur->right;
                }
            }
            return ret;
        }
    

Log in to reply
 

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