LeetCode [1008] Construct Binary Search Tree from Preorder Traversal

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

(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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { int idx; int n; vector<int> nums; TreeNode* helper(int low, int high) { if(idx==n) return NULL; int v = nums[idx]; if(v<low || v>high) return NULL; idx++; TreeNode* node = new TreeNode(v); node->left = helper(low, v); node->right = helper(v, high); return node; } public: TreeNode* bstFromPreorder(vector<int>& preorder) { idx = 0; n = preorder.size(); nums = preorder; return helper(INT_MIN, INT_MAX); } };