C++ Solution, Easy, Clean, Intuitive - O(n) time and O(1) space. beats 90% of submissions.


  • 0
    N
    class Solution {
    public:
        TreeNode* findShortest(TreeNode *root)
        {
            while (root->left)
                root = root->left;
            return root;
        }
        bool find(TreeNode *root, TreeNode *p, TreeNode* &result)
        {
            if (root)
            {
                if (root == p)
                    return true;
                bool left = find(root->left, p, result);
                // the first left side ancestor will be the inorder ancestor
                if (left == true)
                {
                    if (result == NULL)
                        result = root;
                    return true;
                }
                return find(root->right, p, result);
            }
            return false;
        }
        TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
            if (p->right != NULL)
                return findShortest(p->right);
            TreeNode *result = NULL;
            find(root, p, result);
            return result;
        }
    };
    

Log in to reply
 

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