99. 恢复二叉搜索树

发表于 | 分类于
解答并不完全符合题目要求

用时：60min

思路还是中序遍历，使用pre缓存前一个节点，因为中序遍历是递增的，所以一定是先找到大的，再找到小的。

所以第一个出问题的是pre，第二个是root

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
var recoverTree = function(root) {
    var left = null
    var right = null
    var pre = null
    // 一定是先找到大的，再找到小的，所以第一个出问题的是pre，第二个出问题的是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
}