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!

  • 1
    class Solution {
        void recoverTree(TreeNode* root) {
            TreeNode* one = NULL, * two = NULL, *pre = new TreeNode(INT_MIN);
            inorder(root, pre, one, two);
            swap(one->val, two->val);
        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.