Bloomberg recruiter 在 career fair上問的一道題，當(dāng)時(shí)太著急沒想到全部的case棕洋，在recruiter的提醒下終于想清楚了——除了要滿足 leftChild.val < parent.val < rightChild.val 之外拒啰，還要注意當(dāng)前子樹中的所有節(jié)點(diǎn)都要滿足ceiling和floor的約束。
其實(shí)為什么Sedgewick的算法書里面在BST部分要引入ceiling() 和 floor() 這兩個(gè)API，原因是對于一個(gè)合法的Binary Search Tree，其中每一個(gè)節(jié)點(diǎn)，都要滿足小于ceiling大于floor，而一個(gè)節(jié)點(diǎn)的ceiling和floor是由其祖先節(jié)點(diǎn)決定的笋熬。具體而言如下：
如果一個(gè)節(jié)點(diǎn)是其parent的leftChild，則該節(jié)點(diǎn)的ceiling是其parent的value值腻菇，而該節(jié)點(diǎn)的floor則繼承其parent節(jié)點(diǎn)的floor胳螟；
如果一個(gè)節(jié)點(diǎn)是其parent的rightChild，則該節(jié)點(diǎn)的ceiling繼承自其parent的ceiling筹吐，而該節(jié)點(diǎn)的floor則為其parent的value值糖耸。
因此不僅僅是需要將parent的值傳入，而是要傳入<parent.val, floor(parent)> 或者 <ceiling(parent), parent.val> 丘薛，<u>以這種<ceiling, floor>的限制來自上而下驗(yàn)證所有的節(jié)點(diǎn)是否合法嘉竟，所有節(jié)點(diǎn)合法則該BST合法。</u>
*初始的root節(jié)點(diǎn)的值是任意的（廢話），也就意味著 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節(jié)點(diǎn)的 ceiling 和 floor 值設(shè)置問題倦蚪。某一次提交后發(fā)現(xiàn)test case [2147483647] 不通過，2147483647 = 2^31 -1边苹，也就是說這個(gè)case是專門用來考察初始ceiling和floor的設(shè)置的陵且。由于 BST 被當(dāng)做一種 Symbol Table（含有 key-value 結(jié)構(gòu)），key 值默認(rèn)是不相等的勾给，所以通常來說 BST 中左根右的大小關(guān)系是嚴(yán)格的小于而非小于等于滩报。如果初始 root 節(jié)點(diǎn)的 ceiling 值設(shè)為2^31-1 = 2147483647 則會(huì)誤判為非法。
解決辦法為：將 Integer.MAX_VALUE 和 Integer.MIN_VALUE cast 為 long 類型后播急，分別 +1 和 -1脓钾，以此作為 root 節(jié)點(diǎn)的初始 ceiling 和 floor 值。如果不轉(zhuǎn)換為 long桩警，則 +1 和 -1 后會(huì)溢出可训，所得的值無法作為 ceiling 和 floor。
