Comment on page

# 1008.Construct Binary Search Tree from Preorder Traversal

1008.Construct Binary Search Tree from Preorder Traversal

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

1266.png

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;
}
};