Java版LeetCode

Appearance

98. 验证二叉搜索树 ​

树 深度优先搜索 二叉搜索树 二叉树

题目 ​

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

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

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

示例 1：

输入：root = [2,1,3]
输出：true

示例 2：

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

提示：

  • 树中节点数目范围在[1, 104] 内
  • -231 <= Node.val <= 231 - 1

题解 ​

java
/**
 * 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
 * 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
 * 它的左、右子树也分别为二叉排序树。
 * @param root 根节点
 * @return 是否是二叉搜索树
 */
public boolean isValidBST(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    // 中序遍历树
    Consumer<TreeNode> inorderTraversal = new Consumer<TreeNode>() {
        @Override
        public void accept(TreeNode node) {
            if (node == null) {
                return;
            }
            this.accept(node.left);
            list.add(node.val);
            this.accept(node.right);
        }
    };
    inorderTraversal.accept(root);

    // 若中序遍历结果是升序的 则是二叉搜索树 否则不是
    for (int i = 1, length = list.size(); i < length; i++) {
        if (list.get(i - 1) >= list.get(i)) {
            return false;
        }
    }

    return true;
}