正文
leetcode 98,判断二叉树为BST
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
方法一，记录子树的上界和下界，root的左子树一定小于root的值，root的右子树一定大于root的值，然后递归左子树和右子树
public class Solution {
public boolean isValidBST(TreeNode root) {
return isValid(root, null, null);
}
public boolean isValid(TreeNode root, Integer min, Integer max) {
if(root == null) return true;
if(min != null && root.val <= min) return false;
if(max != null && root.val >= max) return false;
return isValid(root.left, min, root.val) && isValid(root.right, root.val, max);
}
}
方法二，中序遍历二叉树，并记录前继节点
public class Solution {
TreeNode prev = null;
/**
* 判断一个树是否为二叉搜索树，使用中序遍历，记录前继节点的值
*
* @param root
* @return
*/
public boolean isValidBST(TreeNode root) {
if (root == null) return true;
//首先找到最左节点的值
TreeNode left = root;
while (left.left != null) {
left = left.left;
}
prev = left;
return isValid(root);
}
private boolean isValid(TreeNode root) {
if (root == null) return true;
if (!isValid(root.left)) return false;
if (root != prev && root.val <= prev.val) return false;
prev = root;
return isValid(root.right);
}
}
