LeetCode 1008 Construct Binary Search Tree from Preorder Traversal

题意

给定一个前序遍历的数组,还原 二叉搜索树

  • 数组中不存在重复值

例 :

1
2
3
4
5
6
7
输入:[8,5,1,7,10,12] 
输出:
8
/ \
5 10
/ \ \
1 7 12

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode bstFromPreorder(int[] preorder) {
if (preorder.length == 0) {
return null;
}

Stack<TreeNode> stack = new Stack<>();
TreeNode root = new TreeNode(preorder[0]);
stack.push(root);

for (int i = 1; i < preorder.length; i++) {
TreeNode temp = stack.peek();
int n = preorder[i];
if (n < temp.val) {
temp.left = new TreeNode(n);
stack.push(temp.left);
} else {
TreeNode prev = stack.pop();
while (!stack.isEmpty() && stack.peek().val < n) {
prev = stack.pop();
}
prev.right = new TreeNode(n);
stack.push(prev.right);
}
}
return root;
}
}

时间复杂度 O(n),空间复杂度 O(n)

Runtime: 1 ms, faster than 82.12% of Java online submissions for Construct Binary Search Tree from Preorder Traversal.

Memory Usage: 36.8 MB, less than 100.00% of Java online submissions for Construct Binary Search Tree from Preorder Traversal.

  • 本文作者: 赵俊
  • 本文链接: http://www.zhaojun.im/leetcode-1008/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!