1008.Construct Binary Search Tree from Preorder Traversal

1008.Construct Binary Search Tree from Preorder Traversal

难度:Medium

返回与给定先序遍历 preorder 相匹配的二叉搜索树(binary search tree)的根结点。

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

示例:

输入:[8,5,1,7,10,12] 输出:[8,5,10,1,7,null,12]

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

执行用时 :4 ms, 在所有 C++ 提交中击败了96.01%的用户 内存消耗 :9 MB, 在所有 C++ 提交中击败了87.58%的用户