98.验证二叉搜索树.md

98. 验证二叉搜索树

url

题目

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

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

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

输入:
    2
   / \
  1   3
输出: true
输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

方法

code

js

let isValidBST = root => {
    let validate = (node, min, max) => {
        if (node === null)
            return true;
        if (node.val <= min || node.val >= max)
            return false;
        return validate(node.left, min, node.val) && validate(node.right, node.val, max);
    }
    return validate(root, Number.MIN_VALUE, Number.MAX_VALUE);
}

go

func isValidBST(root *TreeNode) bool {
	const INT_MAX = int(^uint(0) >> 1)
	const INT_MIN = ^INT_MAX
	var validate func(node *TreeNode, min, max int) bool
	validate = func(node *TreeNode, min, max int) bool {
		if node == nil {
			return true
		}
		if node.Val <= min || node.Val >= max {
			return false
		}
		return validate(node.Left, min, node.Val) && validate(node.Right, node.Val, max)
	}
	return validate(root, INT_MIN, INT_MAX)
}

java

class Solution {
    public boolean isValidBST(TreeNode root) {
        return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    public boolean validate(TreeNode node, long min, long max) {
        if (node == null)
            return true;
        if (node.val <= min || node.val >= max)
            return false;
        return validate(node.left, min, node.val) && validate(node.right, node.val, max);
    }
}