O(1)space, recursive solution in C++.(do not rely on Leetcode about runtime, the same code will get very different result on runtime every time you submit!


  • 0
    Z
    class Solution {
    public:
        void recoverTree(TreeNode* root) {
            TreeNode* one = NULL, * two = NULL, *pre = new TreeNode(INT_MIN);
            inorder(root, pre, one, two);
            swap(one->val, two->val);
        }
        
    private:
        void inorder(TreeNode* root, TreeNode* &pre, TreeNode* &one, TreeNode* &two) {
            if (root != NULL) {
                inorder(root->left, pre, one, two);
                if (pre->val > root->val) {
                    if (one == NULL) one = pre;
                    two = root;
                }
                pre = root;
                inorder(root->right, pre, one, two);
            }
        }
    };

Log in to reply
 

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