forked from kamyu104/LeetCode-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 0
/
construct-binary-tree-from-preorder-and-postorder-traversal.py
60 lines (53 loc) · 1.99 KB
/
construct-binary-tree-from-preorder-and-postorder-traversal.py
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
# Time: O(n)
# Space: O(h)
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution(object):
def constructFromPrePost(self, pre, post):
"""
:type pre: List[int]
:type post: List[int]
:rtype: TreeNode
"""
stack = [TreeNode(pre[0])]
j = 0
for i in xrange(1, len(pre)):
node = TreeNode(pre[i])
while stack[-1].val == post[j]:
stack.pop()
j += 1
if not stack[-1].left:
stack[-1].left = node
else:
stack[-1].right = node
stack.append(node)
return stack[0]
# Time: O(n)
# Space: O(n)
class Solution2(object):
def constructFromPrePost(self, pre, post):
"""
:type pre: List[int]
:type post: List[int]
:rtype: TreeNode
"""
def constructFromPrePostHelper(pre, pre_s, pre_e, post, post_s, post_e, post_entry_idx_map):
if pre_s >= pre_e or post_s >= post_e:
return None
node = TreeNode(pre[pre_s])
if pre_e-pre_s > 1:
left_tree_size = post_entry_idx_map[pre[pre_s+1]]-post_s+1
node.left = constructFromPrePostHelper(pre, pre_s+1, pre_s+1+left_tree_size,
post, post_s, post_s+left_tree_size,
post_entry_idx_map)
node.right = constructFromPrePostHelper(pre, pre_s+1+left_tree_size, pre_e,
post, post_s+left_tree_size, post_e-1,
post_entry_idx_map)
return node
post_entry_idx_map = {}
for i, val in enumerate(post):
post_entry_idx_map[val] = i
return constructFromPrePostHelper(pre, 0, len(pre), post, 0, len(post), post_entry_idx_map)