/** * 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; * } * } */ publicclassSolution { /** * @param root: The root of binary tree. * @return: True if the binary tree is BST, or false */ publicbooleanisValidBST(TreeNode root) { if (root == null) returntrue;
privatebooleanhelper(TreeNode root, long lower, long upper) { if (root == null) returntrue; // System.out.println("root.val = " + root.val + ", lower = " + lower + ", upper = " + upper); // left node value < root node value < right node value if (root.val >= upper || root.val <= lower) returnfalse; booleanisLeftValidBST= helper(root.left, lower, root.val); booleanisRightValidBST= helper(root.right, root.val, upper);
return isLeftValidBST && isRightValidBST; } }
源码分析
为避免节点中出现整型的最大最小值,引入 long 型进行比较。有些 BST 的定义允许左子结点的值与根节点相同,此时需要更改比较条件为root.val > upper. C++ 中 long 可能与 int 范围相同,故使用 long long. 如果不使用比 int 型更大的类型,那么就需要在相等时多加一些判断。