# 1008.Construct Binary Search Tree from Preorder Traversal

(回想一下，二叉搜索树是二叉树的一种，其每个节点都满足以下规则，对于 node.left 的任何后代，值总 < node.val，而 node.right 的任何后代，值总 > node.val。此外，先序遍历首先显示节点的值，然后遍历 node.left，接着遍历 node.right。）

1 <= preorder.length <= 100 先序 preorder 中的值是不同的。

`/** * 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 {public:    TreeNode* bstFromPreorder(vector<int>& preorder) {        TreeNode* root = new TreeNode(preorder[0]);​        stack<TreeNode*> s;        s.push(root);        for(int i=1;i<preorder.size();i++)        {            TreeNode* cur = s.top();            if(preorder[i] <cur->val )             {                cur->left = new TreeNode(preorder[i]);               s.push(cur->left);​​            }            else            {                while( s.size()>1 &&  cur->val < preorder[i])                {                s.pop();                cur = s.top();                }                if( cur->val < preorder[i]){                while(cur->right)                {                    s.push(cur->right);                    cur=cur->right;                }                 cur->right = new TreeNode(preorder[i]);                }                else{                    s.push(cur->left);                    cur=cur->left;                while(cur->right )                {                    s.push(cur->right);                    cur=cur->right;                }                // cout<<cur->val<<endl;​​                cur->right = new TreeNode(preorder[i]);​                }                s.push(cur->right);​            }​​        }        return root;    }};`