Leetcode题解
Search…
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 中的值是不同的。
先序遍历，先遍历根节点和左孩子，然后到底之后再遍历右边的。不断回溯。
所以当下一个节点比当前节点小时，直接添加左孩子即可。 当其比较大时，不断回溯比较，找到大于该节点的根节点，然后从其左子树开始比较，如果不存在右孩子，则将其添加为右孩子。如果有，则比较其右孩子的右孩子(左边之前已经遍历过了)，不断循环，最后将其添加为右孩子即可。
代码实现如下：
1
/**
2
* Definition for a binary tree node.
3
* struct TreeNode {
4
* int val;
5
* TreeNode *left;
6
* TreeNode *right;
7
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8
* };
9
*/
10
class Solution {
11
public:
12
TreeNode* bstFromPreorder(vector<int>& preorder) {
13
TreeNode* root = new TreeNode(preorder[0]);
14
15
stack<TreeNode*> s;
16
s.push(root);
17
for(int i=1;i<preorder.size();i++)
18
{
19
TreeNode* cur = s.top();
20
if(preorder[i] <cur->val )
21
{
22
cur->left = new TreeNode(preorder[i]);
23
s.push(cur->left);
24
25
26
}
27
else
28
{
29
while( s.size()>1 && cur->val < preorder[i])
30
{
31
s.pop();
32
cur = s.top();
33
}
34
if( cur->val < preorder[i]){
35
while(cur->right)
36
{
37
s.push(cur->right);
38
cur=cur->right;
39
}
40
cur->right = new TreeNode(preorder[i]);
41
}
42
else{
43
s.push(cur->left);
44
cur=cur->left;
45
while(cur->right )
46
{
47
s.push(cur->right);
48
cur=cur->right;
49
}
50
// cout<<cur->val<<endl;
51
52
53
cur->right = new TreeNode(preorder[i]);
54
55
}
56
s.push(cur->right);
57
58
}
59
60
61
}
62
return root;
63
}
64
};
Copied!
执行用时 :4 ms, 在所有 C++ 提交中击败了96.01%的用户 内存消耗 :9 MB, 在所有 C++ 提交中击败了87.58%的用户
Copy link