98. 验证二叉搜索树

发表于 | 分类于
愉快的周末从AC开始 （真

用时 10min

直接用二叉搜索树中序遍历递增的性质就好了

  1. 中序遍历找到左孩子
  2. pre 是否存在
  3. 不存在，赋值 ，找右孩子，返回 1
  4. 存在，是否比 val 小
  5. 是，非递增，返回 false
  6. 否，递增，赋值 pre ，返回 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var isValidBST = function(root) {
    var preVal = null
    var DFS = function(root) {
        var left = true
        var right = true
        if (root.left) {
            left =  DFS(root.left)
        }
        if (preVal !== null) {
            if (preVal >= root.val) return false
            preVal = root.val
        } else {
            preVal = root.val
        }
        if (root.right) {
            right =  DFS(root.right)
        }
        return left && right
    }
    return DFS(root)
};