Bloomberg recruiter 在 career fair上问的一道题，当时太着急没想到全部的case，在recruiter的提醒下终于想清楚了——除了要满足 leftChild.val < parent.val < rightChild.val 之外，还要注意当前子树中的所有节点都要满足ceiling和floor的约束。
其实为什么Sedgewick的算法书里面在BST部分要引入ceiling() 和 floor() 这两个API，原因是对于一个合法的Binary Search Tree，其中每一个节点，都要满足小于ceiling大于floor，而一个节点的ceiling和floor是由其祖先节点决定的。具体而言如下：
如果一个节点是其parent的leftChild，则该节点的ceiling是其parent的value值，而该节点的floor则继承其parent节点的floor；
如果一个节点是其parent的rightChild，则该节点的ceiling继承自其parent的ceiling，而该节点的floor则为其parent的value值。
因此不仅仅是需要将parent的值传入，而是要传入<parent.val, floor(parent)> 或者 <ceiling(parent), parent.val> ，<u>以这种<ceiling, floor>的限制来自上而下验证所有的节点是否合法，所有节点合法则该BST合法。</u>
*初始的root节点的值是任意的（废话），也就意味着 ceiling 和 floor是[-∞, +∞]，程序中可表示的整型最大值（4 bytes）为 2^31-1, Java 中整型最大值最小值分别为 Integer.MAX_VALUE 与 Integer.MIN_VALUE.
代码如下：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution
{
public boolean isValidBST(TreeNode root)
{
long ceiling = (long) Integer.MAX_VALUE + 1;
long floor = (long) Integer.MIN_VALUE - 1;
return isValidBSTHelper(root, ceiling, floor);
}
public boolean isValidBSTHelper(TreeNode node, long ceiling, long floor)
{
if(node == null)
return true;
else if(node.val >= ceiling || node.val <= floor)
return false;
else
{
boolean isValidLeft = isValidBSTHelper(node.left, node.val, floor);
boolean isValidRight = isValidBSTHelper(node.right, ceiling, node.val);
return isValidLeft && isValidRight;
}
}
}
需要注意的是其中初始的root节点的 ceiling 和 floor 值设置问题。某一次提交后发现test case [2147483647] 不通过，2147483647 = 2^31 -1，也就是说这个case是专门用来考察初始ceiling和floor的设置的。由于 BST 被当做一种 Symbol Table（含有 key-value 结构），key 值默认是不相等的，所以通常来说 BST 中左根右的大小关系是严格的小于而非小于等于。如果初始 root 节点的 ceiling 值设为2^31-1 = 2147483647 则会误判为非法。
解决办法为：将 Integer.MAX_VALUE 和 Integer.MIN_VALUE cast 为 long 类型后，分别 +1 和 -1，以此作为 root 节点的初始 ceiling 和 floor 值。如果不转换为 long，则 +1 和 -1 后会溢出，所得的值无法作为 ceiling 和 floor。
