Time: 60 minutes

The idea is still in-order traversal, using pre to cache the previous node. Because the in-order traversal is incremental, you must find the larger one first and then the smaller one.

So the first problem is pre, the second is root

var recoverTree = function(root) {
    var left = null    var right = null    var pre = null    // You must find the big one first, then the small one, so the first one to have a problem is pre, and the second one to have a problem is root var DFS = function (root) {
        if (root.left) {
            DFS(root.left)
        }
        if (pre) {
            console.log(pre.val)
            if (pre.val > root.val) {
                if(!left) {
                    left = pre
                    right = root                } else {
                    right = root                }
            }
            pre = root        } else {
            pre = root        }
        if (root.right) {
            DFS(root.right)
        }
    }
    DFS(root)
    if (left && right) {
        [left.val,right.val] = [right.val,left.val]
    }
    return root}