算法之验证二叉搜索树 - 翁先森的博客

98. 验证二叉搜索树 #

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

解法：

1.递归

思路：

根据二叉搜索树的特性：

中序遍历的时候遍历的顺序是由小到大逐渐遍历的，也就是升序排列，

所以我们保存上一个值prev，与当前值current作比较。

如果当前值小于等于上一个值，那么这个树不是二叉搜索树。

1
/**
2
 * Definition for a binary tree node.
3
 * function TreeNode(val, left, right) {
4
 *     this.val = (val===undefined ? 0 : val)
5
 *     this.left = (left===undefined ? null : left)
6
 *     this.right = (right===undefined ? null : right)
7
 * }
8
 */
9
/**
10
 * @param {TreeNode} root
11
 * @return {boolean}
12
 */
13
var isValidBST = function (node) {
14
    var prev = -Infinity
15

16
    function inorder(node) {
17
        if (!node) {
18
            return true
19
        }
20

21
        var preResult = inorder(node.left)
22
        var inResult = node.val > prev
23
        prev = node.val
24
        var postResult = inorder(node.right)
25
        return preResult && inResult && postResult
26
    }
27

28
    return  inorder(node)
29
}

2.非递归（迭代）

1
var isValidBST = function (node) {
2
    var stack = []
3
    var prev = -Infinity
4

5
    while(stack.length || node) {
6
        while(node) {
7
            stack.push(node)
8
            node = node.left
9
        }
10

11
        node = stack.pop()
12

13
        if (node.val <= prev) {
14
            return false
15
        }
16

17
        prev = node.val
18
        node = node.right
19
    }
20

21
    return true
22
}

98. 验证二叉搜索树#

98. 验证二叉搜索树 #