## Wednesday, November 23, 2016

### Max subtree in BST in range A and B - Google

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

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. }
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;

Line 17 and Line 19 多余的，请忽略。因为post-order traversal时已经检查过左右child nodes了。

1. // global variables.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
2. int low, high; // range low and high bounds.鏈枃鍘熷垱鑷�1point3acres璁哄潧
3. int maxSubTreeSize = 0; // max subtree size in [low,high]

4. struct Node {
5.   int val; Node* left, *right;
6.   Node(int v) :val(v), left(NULL), right(NULL) {}
7. };

8. // true if tree rooted at x is in range [low,high]
9. // count: node count if tree in range
10. bool checkRange(Node* x, int& count) {
11.   if (!x) { count = 0; return true; }
12.   int leftCount, rightCount;
13.   // do post-order traversal to update maxSubTreeSize
14.   bool leftInRange = checkRange(x->left, leftCount);
15.   if (leftInRange) maxSubTreeSize = max(maxSubTreeSize, leftCount);
16.   bool rightInRange = checkRange(x->right, rightCount);
17.   if (rightInRange) maxSubTreeSize = max(maxSubTreeSize, rightCount);
18.   if (leftInRange && rightInRange && x->val >= low && x->val <= high) {. From 1point 3acres bbs
19.     count = leftCount + rightCount + 1;
20.     maxSubTreeSize = max(maxSubTreeSize, count);
21.     return true;
22.   }
23.   else return false;
24. }

25. int getMaxSubTreeSize(Node* r, int a, int b) {
26.   low = a; high = b; int count = 0;
27.   checkRange(r, count);
28.   return maxSubTreeSize;
29. }