验证二叉搜索树java实现_验证二叉搜索树 java

方法一：二叉树的中序遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        //二叉树有一个特点在于它的中序遍历结果升序排列
        //定义一个栈用于控制中序遍历的顺序
        Stack<TreeNode> stack = new Stack<>();
        //定义起始节点
        TreeNode cur = root;
        long pre = Long.MIN_VALUE;
        //循环中序遍历
        while(!stack.isEmpty() || cur != null){
            //首先将本节点的左节点全部入栈
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            //出栈第一个节点
            cur = stack.pop();
            //对节点判断是否符合条件
            if(pre >= cur.val){
                return false;
            }
            pre = cur.val;
            //继续判断右子树
            cur = cur.right;
        }
        return true;
    }
}
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
32
33
34
35
36
37
38
39
40
41
42
43

方法二：逐个递归验证

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        return check(root,Long.MIN_VALUE,Long.MAX_VALUE);
    }

    private boolean check(TreeNode root,long left,long right){
        //设置递归出口
        if(root == null){
            return true;
        }
        //判断当前值是否满足条件
        if(left >= root.val || root.val >= right){
            return false;
        }
        //递归遍历左右子树是否满足条件,遍历左子树时将当前的节点的值作为右边界，遍历右子树时减当前节点作为左边界
        return check(root.left,left,(long)root.val) && check(root.right,(long)root.val,right);
    }
}
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
32
33