# Leetcode: Construct Binary Tree from Preorder and Postorder Traversal

Construct Binary Tree from Preorder and Postorder Traversal

Similar Problems:

Return any binary tree that matches the given preorder and postorder traversals.
Values in the traversals pre and post are distinct positive integers.

Example 1:

```Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]
```

Note:

1. 1 <= pre.length `= post.length <` 30
2. pre[] and post[] are both permutations of 1, 2, …, pre.length.
3. It is guaranteed an answer exists. If there exists multiple answers, you can return any of them.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

• Solution:
```// Blog link: https://code.dennyzhang.com/construct-binary-tree-from-preorder-and-postorder-traversal
// Basic Ideas:
// Complexity: Time ?, Space O?
/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func constructFromPrePost(pre []int, post []int) *TreeNode {
if len(pre) == 0 { return nil }
res := &TreeNode{pre[0], nil, nil}
if len(pre) == 1 { return res }
for i:=len(pre)-1; i>=0; i-- {
if post[i] == pre[1] {
res.Left = constructFromPrePost(pre[1:i+2], post[0:i+1])
res.Right = constructFromPrePost(pre[i+2:], post[i+1:len(pre)-1])
break
}
}
return res
}
```

Share It, If You Like It.