Split BST with Threshold

来源：Google onsite

原帖：来自于一亩三分地或meetqun上的面经

题目：
Given a binary search tree (BST) and a threshold. Split the BST into 2 BST according to
a threshold, one BST is smaller than threshold; the other one is larger than threshold.

思路：
Google的onsite题目，第一次看到这道题的时候完全没有思路。后来仔细思考一下，发现只要考虑到split的时机，然后recursion即可以解这道题。

代码：

 struct TreeNode {   
   int val;   
   TreeNode* left, *right;   
   TreeNode(int v) : val(v), left(NULL), right(NULL) {};   
 };  
    
 void splitTree(TreeNode* root, TreeNode* &t1, TreeNode* &t2, int threshold) {   
   if (!root) return;   
   if (root->val == threshold) {   
     t1 = root->left;   
     t2 = root->right;   
     return;   
   } else if (root->val > threshold) {   
     TreeNode* left = NULL, *right = NULL;   
     splitTree(root->left, left, right, threshold);   
     t2 = root;    
     t2->left = right;   
     t1 = left;   
   } else {   
     TreeNode* left = NULL, *right = NULL;   
     splitTree(root->right, left, right, threshold);   
     t1 = root;   
     t1->right = left;   
     t2 = right;   
   }   
 }   
     
 TreeNode *buildBST(vector<int>& num, int start, int end) {   
   if (start < end) return NULL;   
   int mid = start + (end - start) / 2;   
   TreeNode *root = new TreeNode(num[mid]);   
   root->left = buildBST(num, start, mid - 1);   
   root->right = buildBST(num, mid + 1, end);   
   return root;   
 }   
     
 TreeNode *sortedArrayToBST(vector<int>& num) {   
   return buildBST(num, 0, num.size() - 1);   
 }   
      
 void inorder(TreeNode* root, vector<int>& num) {   
   if (!root) return;   
   inorder(root->left, num);   
   num.push_back(root->val);   
   inorder(root->right, num);   
 }  
   
 int main() {   
   vector<int> num = {1,2,3,4,5,6,7,8,9,10,11,13};   
   int thr = 5;   
     
   TreeNode* root = sortedArrayToBST(num);   
   TreeNode* left = NULL, *right = NULL;   
   splitTree(root, left, right, thr);   
   
   vector<int> l_num, r_num;   
   inorder(left, l_num);   
   inorder(right, r_num);   
   
   for(auto i : l_num) cout << i << " ";   
   cout << endl;   
   for(auto i : r_num) cout << i << " ";   
   cout << endl;   
   return 0;  
 }