Max subtree in BST in range A and B - Google

http://www.1point3acres.com/bbs/thread-206843-1-1.html

第二题 求一个二叉查找数中，最大的subtree的size。subtree所有元素都必须在范围[A,B]之间。O(n)。

这个题是找最大的满足条件的subtree，一个subtree是必须某个node和其所有子孙nodes. 在判断 “if(left<=root->val&&right>=root->val) {  res=1+left_num+right_num;  }”时，应该先判断left/right subtree是否满足条件再更新res吧。这个help function应该加一个invalid default return value (any negative value is OK)，表示该subtree不是在[left, right]范围内的。否则例如对于一个简单的3 nodes的tree：root=1, left node = 100, right node = 100, 范围[0, 2]，本来是没有这样的subtree，但原code返回1. 
稍改动加个default value就可以了。

left_sum 和 right_sum应该check是不是-1？是的话说明subtree已经不合法了，然后直接返回-1？最后检测root.val 的时候也应该是如果它不在范围里面直接返回-1？

1. int Result; // global variable to store node count of max valid subtree
2. . Waral 鍗氬鏈夋洿澶氭枃绔�,
3. // main function. Waral 鍗氬鏈夋洿澶氭枃绔�,
4. int getSubTreeSize(Node* root, int left, int right) {
5.   Result = -1; // default node count if subtree invalid
6.   helper(root, left, right);
7.   return Result;
8. }
9. -google 1point3acres
10. // get node count of subtree rooted at "root" if valid; otherwise, return -1
11. int helper(Node* root, int left, int right) {
12.   if (root == NULL) return 0;
13.   int left_num = helper(root->left, left, right);
14.   int right_num = helper(root->right, left, right);
15.   int res = -1; // default node count if subtree invalid
16.   if (left_num >= 0 && right_num >= 0 && left <= root->val && right >= root->val) {.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
17.     res = left_num + right_num + 1; // update node count only if valid
18.     Result = max(Result, res); // update global result
19.   }. From 1point 3acres bbs
20.   return res;
21. }

1. //maxsubsize
2.     public static class TreeNode{
3.     TreeNode left;
4.     TreeNode right;
5.     int val;
6.     public TreeNode(int val){
7.       this.val = val;
8.     } 
9.   }
10. static int max = -1;
11. public static int maxSubsize(int A, int B, TreeNode root){
12.   if(root == null) return 0;
13.   if(root.val < A || root.val > B) return -1;.1point3acres缃�
14.   int left = maxSubsize(A, B, root.left);
15.   int right = maxSubsize(A, B, root.right);
16.   if(left == -1 || right == -1){
17.     return -1;
18.   }
19.   if(left != -1 && right != -1){.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
20.     max = Math.max(1 + left + right, max);
21.     return 1 + left + right;.1point3acres缃�
22.   }
23.   return -1;
24. }

Line 14: if(root.val < A || root.val > B) return -1;
这一行不应该立即返回吧。这样如果root node value一旦不在区间[A,B]范围内就不再检查子树范围了。例如给定范围[3,4]和一个3结点的tree: root = 1, left child = 2, right child = 3. 最大subtree size应该是1，不应该返回-1.

Line 17 and Line 19 多余的，请忽略。因为post-order traversal时已经检查过左右child nodes了。
第二题 求一个二叉查找数中，最大的subtree的size in range [A, B]。
因为一个tree的node范围是否在区间[A,B]可以很容易由他的左右子树的范围以及根的value来决定，所以可以用post-order traversal O(N)时间遍历整个tree, 同时注意不断更新最大满足区间范围子树的node count. 注意：在遍历过程中，若判定一个子树满足区间范围时一定要及时记录其node count以备parent trees使用。

1. // global variables.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
2. int low, high; // range low and high bounds.鏈枃鍘熷垱鑷�1point3acres璁哄潧
3. int maxSubTreeSize = 0; // max subtree size in [low,high]
4. 
   
5. struct Node {
6.   int val; Node* left, *right;
7.   Node(int v) :val(v), left(NULL), right(NULL) {}
8. };
9. 
   
10. // true if tree rooted at x is in range [low,high]
11. // count: node count if tree in range
12. bool checkRange(Node* x, int& count) { 
13.   if (!x) { count = 0; return true; }
14.   int leftCount, rightCount;
15.   // do post-order traversal to update maxSubTreeSize
16.   bool leftInRange = checkRange(x->left, leftCount);
17.   if (leftInRange) maxSubTreeSize = max(maxSubTreeSize, leftCount);
18.   bool rightInRange = checkRange(x->right, rightCount); 
19.   if (rightInRange) maxSubTreeSize = max(maxSubTreeSize, rightCount);
20.   if (leftInRange && rightInRange && x->val >= low && x->val <= high) {. From 1point 3acres bbs
21.     count = leftCount + rightCount + 1;
22.     maxSubTreeSize = max(maxSubTreeSize, count);
23.     return true;
24.   }
25.   else return false;
26. }
27. 
    
28. int getMaxSubTreeSize(Node* r, int a, int b) {
29.   low = a; high = b; int count = 0;
30.   checkRange(r, count);
31.   return maxSubTreeSize;
32. }