Comment on page
889. Construct Binary Tree from Preorder and Postorder Traversal
Medium
Given two integer arrays,
preorder
and postorder
where preorder
is the preorder traversal of a binary tree of distinct values and postorder
is the postorder traversal of the same tree, reconstruct and return the binary tree.If there exist multiple answers, you can return any of them.
Example 1:

Input: preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]
Example 2:
Input: preorder = [1], postorder = [1]
Output: [1]
Constraints:
1 <= preorder.length <= 30
1 <= preorder[i] <= preorder.length
- All the values of
preorder
are unique. postorder.length == preorder.length
1 <= postorder[i] <= postorder.length
- All the values of
postorder
are unique. - It is guaranteed that
preorder
andpostorder
are the preorder traversal and postorder traversal of the same binary tree.
Runtime: 0 ms, faster than 100%
Memory Usage: 3.3 MB, less than 69.57%
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func constructFromPrePost(preorder []int, postorder []int) *TreeNode {
// pre 中左右
// post 左右中
l := len(postorder)
if l == 0 { return nil }
if l == 1 { return &TreeNode{ Val: preorder[0] }}
n := preorder[0]
left := preorder[1]
for i:=0; i<l; i++ {
if postorder[i] == left {
return &TreeNode{
Val: n,
Left: constructFromPrePost(preorder[1:i+2], postorder[:i+1]),
Right: constructFromPrePost(preorder[i+2:], postorder[i+1: l-1]),
}
}
}
return nil
}
Last modified 8mo ago