time O(N)
space O(H)
State Variables
Data Given:
preorder1, 2, 4, 5, 3, 6, 7
postorder4, 5, 2, 6, 7, 3, 1
preIdx0
postIdx0
Start construction. preIndex = 0, postIndex = 0.
Pseudocode
Pseudocode
1function constructFromPrePost(pre, post):
2 preIndex = 0, postIndex = 0
3 function construct():
4 node = new TreeNode(pre[preIndex++])
5 if node.val != post[postIndex]:
6 node.left = construct()
7 if node.val != post[postIndex]:
8 node.right = construct()
9 postIndex++
10 return node
11 return construct()