098. 验证二叉查找树

发表于 | 分类于 | 阅读次数:

验证二叉查找树

英文版
中文版

这里使用树的中序遍历方法，参考树的中序-非递归遍历

注意一个错误 else分支中 cur = cur.right 是错误的！！！

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * @description: 验证二叉搜索树
 * @author: rhsphere
 * @since: 2019-11-05 09:37 by jdk 1.8
 */
public class IsValidBST {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    public boolean isValidBST(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        double inorder = -Double.MAX_VALUE;
        while (!stack.empty() || cur != null) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                TreeNode node = stack.pop();
                if (node.val <= inorder)
                    return false;
                inorder = node.val;
                cur = node.right;
            }
        }
        return true;
    }
}

题目

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

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

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

示例 1:

输入:
2
/ \
1 3
输出: true
示例 2:

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

0%