1008. Construct Binary Search Tree from Preorder Traversal

Return the root node of a binary search tree that matches the given preorder traversal.

(Recall that a binary search tree is a binary tree where for every node, any descendant of node.left has a value < node.val, and any descendant of node.right has a value > node.val. Also recall that a preorder traversal displays the value of the node first, then traverses node.left, then traverses node.right.)

Example 1:

Input: [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]

Note:

1. 1 <= preorder.length <= 100

2. The values of preorder are distinct.

TreeNode* helper(vector<int>& preorder, int L, int R) {
    if (L > R) return nullptr;
    TreeNode* cur = new TreeNode(preorder[L]);
    if (L == R) return cur;
    int i = L;
    while (i < preorder.size() && preorder[i] <= preorder[L]) ++i;
    cur->left = helper(preorder, L + 1, i - 1);
    cur->right = helper(preorder, i, R);
    return cur;
}
TreeNode* bstFromPreorder(vector<int>& preorder) { // time: O(n^2); space: O(h)
    return helper(preorder, 0, preorder.size() - 1);
}

在Recursion的過程同時紀錄從這往左或往右下去的subtree最大值是多少可以幫助我們節省每一層中搜尋分界點的操作，達到O(n)的結果。

TreeNode* helper(vector<int>& preorder, int& i, int upper) {
    if (i == preorder.size() || preorder[i] > upper) return nullptr;
    TreeNode* root = new TreeNode(preorder[i++]);
    root->left = helper(preorder, i, root->val);
    root->right = helper(preorder, i, upper);
    return root;
}
TreeNode* bstFromPreorder(vector<int>& preorder) { // time: O(n); space: O(h)
    int i = 0;
    return helper(preorder, i, INT_MAX);
}