描述
给定一个二叉树，判断它是否是合法的二叉查找树(BST)
一棵 BST 定义为：
节点的左子树中的值要严格小于该节点的值。
节点的右子树中的值要严格大于该节点的值。
左右子树也必须是二叉查找树。
一个节点的树也是二叉查找树。
如果题目像本题一样有特殊要求则 BST 定义按题目要求来，如果题目没有要求则默认定义如下
二叉查找树性质
二叉查找树功能
O(h)的时间查找，删除，和插入
样例
一个例子：
2
/ \
1 4
/ \
3 5
上述这棵二叉树序列化为 {2,1,4,#,#,3,5}
PS
本题其实是简化版的二叉查找树的考题，因为题目去掉了等于的情形，如果考虑等于代码要更复杂
代码
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
- 分治
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
class ResultType{
boolean is_bst;
int minValue, maxValue;
ResultType(boolean is_bst, int minValue, int maxValue) {
this.is_bst = is_bst;
this.minValue = minValue;
this.maxValue = maxValue;
}
}
public class Solution {
/**
* @param root: The root of binary tree.
* @return: True if the binary tree is BST, or false
*/
public boolean isValidBST(TreeNode root) {
ResultType r = validateHelper(root);
return r.is_bst;
}
private ResultType validateHelper(TreeNode root) {
// 注意此处返回值，minValue 对应 Integer.MAX_VALUE，maxValue 对应 Integer.MIN_VALUE，否则叶子结点会报错
// 对空指针必须要有返回值，对于 root 取非 Integer.MIN_VALUE, Integer.MAX_VALUE 两个数的情况下，程序正常
if (root == null) {
return new ResultType(true, Integer.MAX_VALUE, Integer.MIN_VALUE);
}
ResultType left = validateHelper(root.left);
ResultType right = validateHelper(root.right);
if (!left.is_bst || !right.is_bst) {
return new ResultType(false, 0, 0);
}
// 如果不对 root.left 和 root.right 做非空判断，当根结点值为 Integer.MIN_VALUE, Integer.MAX_VALUE 时会因为上面对空结点的返回值出现错误判断
if (root.left != null && left.maxValue >= root.val ||
root.right != null && right.minValue <= root.val) {
return new ResultType(false, 0, 0);
}
// 左右儿子是null时，返回Integer.MAX_VALUE和Integer.MIN_VALUE
// 所以要和root.val进行比较
// (如果左右儿子不为空其实没必要比较，但程序的必须保证鲁棒性才能运行)
int minValue = Math.min(root.val, left.minValue);
int maxValue = Math.max(root.val, right.maxValue);
return new ResultType(true, minValue, maxValue);
}
}
- 第二种分治：
public class Solution {
/**
* @param root: The root of binary tree.
* @return: True if the binary tree is BST, or false
*/
public boolean isValidBST(TreeNode root) {
return divConq(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean divConq(TreeNode root, long min, long max){
if (root == null){
return true;
}
// root值和左子树最大值，右子树最小值进行比较
if (root.val <= min || root.val >= max){
return false;
}
// 把赋值和判断都写到了一起
return divConq(root.left, min, Math.min(max, root.val)) &&
divConq(root.right, Math.max(min, root.val), max);
}
}
两种分治本质上没什么区别
- 遍历
思路
BST 有一个性质，就是它的中序遍历是递增的，因此我们按照中序遍历的过程，判断始终是递增的，那么这就是 BST，什么样的情况是递增的，就是当前遍历的结点始终大于前一个，则递增。firstNode 用于表示是否是中序遍历的第一个结点，lastVal 表示上一个结点的值，因为第一个结点是没有前结点的，也就没有了 lastVal 与当前结点的比较。
每一轮递归都要面临判断是否是中序遍历的第一个结点
public class Solution {
private int lastVal = Integer.MIN_VALUE;
private boolean firstNode = true;
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
// 左子树不是 BST
if (!isValidBST(root.left)) {
return false;
}
if (!firstNode && lastVal >= root.val) {
return false;
}
firstNode = false;
lastVal = root.val;
// 右子树不是 BST
if (!isValidBST(root.right)) {
return false;
}
return true;
}
}
