# 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`.)

It’s guaranteed that for the given test cases there is always possible to find a binary search tree with the given requirements.

Example 1:

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

Constraints:

• `1 <= preorder.length <= 100`
• `1 <= preorder[i] <= 10^8`
• The values of `preorder` are distinct.

``````class Solution {
public:
TreeNode* bstFromPreorder(vector<int>& preorder) {
if (preorder.empty()) return nullptr;
TreeNode *node = new TreeNode(preorder[0]);
int i = 0, n = preorder.size();
for (i = 1; i < n; ++i) {
if (preorder[i] > preorder[0]) break;
}
vector<int> left(preorder.begin() + 1, preorder.begin() + i);
vector<int> right(preorder.begin() + i, preorder.end());
node->left = bstFromPreorder(left);
node->right = bstFromPreorder(right);
return node;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1008

Construct Binary Tree from Preorder and Postorder Traversal

Construct Binary Tree from Inorder and Postorder Traversal

Construct Binary Tree from Preorder and Inorder Traversal

https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal/

https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal/discuss/252754/Java-Stack-Iterative-Solution

https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal/discuss/252232/JavaC%2B%2BPython-O(N)-Solution

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation