Inorder traversal.

e.g. [1,2,3,4,5,6,7] => [1,2,3,5,4,6,7]; then first would be 5, second 4; i.e. should be all ascending, there’re 2 cases where prev > cur now. root is cur in recursion.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public void recoverTree(TreeNode root) {
        TreeNode first=null, second = null;
        TreeNode pre = new TreeNode(Integer.MIN_VALUE);
        public void recoverTree(TreeNode root) {
            inorder(root);
            int tmp = first.val;
            first.val = second.val;
            second.val = tmp;
        }
        public void inorder(TreeNode root) {
            if (root == null) return;
            inorder(root.left);
            if (first == null && pre.val >= root.val) first = pre;
            if (first != null && pre.val >= root.val) second = root;
            pre = root;
            inorder(root.right);
        }
    }
}

Above is O(n). Morris Traversal would be O(1).

https://leetcode.com/problems/recover-binary-search-tree/solution/