题目描述
给定一个二叉树,判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征:
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例:
输入: 2 / \ 1 3 输出: true
递归思路
1.二叉搜索树的性质是根节点的左子树都比根节点小,根节点的右子树都比根节点大。
2.给每个节点设置最大值和最小值,若符合该节点值在合法区间内,则对其子节点继续递归,递归出口为节点为NULL。
Java代码实现
public boolean isValidBST(TreeNode root) { return isValidBST(root,null,null); } private boolean isValidBST(TreeNode root,Integer min,Integer max) { if(root == null) return true; int val = root.val; if((min != null && val <= min) || (max != null && val >= max)) return false; return isValidBST(root.left,min,val) && isValidBST(root.right,val,max); }
中序遍历思路
1.二叉搜索数还有一个重要的性质是,中序遍历得到的结果是一个递增序列。
Java代码实现
public boolean isValidBST(TreeNode root) { Stack<TreeNode> stack = new Stack(); Integer min = null; while(root != null || !stack.isEmpty()){ while(root != null){ stack.push(root); root = root.left; } TreeNode node = stack.pop(); if(min != null && node.val <= min) return false; min = node.val; root = node.right; } return true; }