题目描述

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

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

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

题目分析

递归

对于二叉搜索树 t 来说：
– 左子树是二叉搜索树，且所有结点值小于 t
– 右子树是二叉搜索树，且所有结点值大于 t

因此可以递归判断，核心是每次都把最大值和最小值的限制传递下去

中序遍历

使用中序遍历，把二叉树转成数组，再判断数组是否有序即可

Java

public boolean isValidBST(TreeNode root) {
    return isValidBST(root, null, null);
}

public boolean isValidBST(TreeNode root, Integer minValue, Integer maxValue) {
    if (root == null) {
        return true;
    }
    int value = root.val;
    if ((minValue != null && value <= minValue) || (maxValue != null && value >= maxValue)) {
        return false;
    }

    return isValidBST(root.left, minValue, value) && isValidBST(root.right, value, maxValue);
}

public boolean isValidBST2(TreeNode root) {
    List<Integer> list = dfs(root);
    for (int i = 0; i < list.size(); i++) {
        if (i >= 1 && list.get(i) <= list.get(i - 1)) {
            return false;
        }
    }
    return true;
}

private List<Integer> dfs(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    if (root == null) {
        return list;
    }
    list.addAll(dfs(root.left));
    list.add(root.val);
    list.addAll(dfs(root.right));
    return list;
}

Kotlin

fun isValidBST(root: TreeNode?, minValue: Int? = null, maxValue: Int? = null): Boolean {
    if (root == null) {
        return true
    }
    val value = root.`val`
    if ((minValue != null && value <= minValue) || (maxValue != null && value >= maxValue)) {
        return false
    }

    return isValidBST(root.left, minValue, value) && isValidBST(root.right, value, maxValue)
}


fun isValidBST(root: TreeNode?): Boolean {
    val list = dfs(root)
    for (i in list.indices) {
        if (i >= 1 && list[i] <= list[i - 1]) {
            return false
        }
    }
    return true
}

private fun dfs(root: TreeNode?): List<Int> {
    val ans = ArrayList<Int>()
    if (root == null) {
        return ans
    }
    ans.addAll(dfs(root.left))
    ans.add(root.`val`)
    ans.addAll(dfs(root.right))
    return ans
}