0106. Construct Binary Tree From Inorder and Postorder Traversal

# 106. Construct Binary Tree from Inorder and Postorder Traversal#

## 题目 #

Given inorder and postorder traversal of a tree, construct the binary tree.

Note: You may assume that duplicates do not exist in the tree.

For example, given

``````inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]
``````

Return the following binary tree:

``````    3
/ \
9  20
/  \
15   7
``````

## 解题思路 #

• 给出 2 个数组，根据 inorder 和 postorder 数组构造一颗树。
• 利用递归思想，从 postorder 可以得到根节点，从 inorder 中得到左子树和右子树。只剩一个节点的时候即为根节点。不断的递归直到所有的树都生成完成。

## 代码 #

``````
package leetcode

import (
"github.com/halfrost/leetcode-go/structures"
)

// TreeNode define
type TreeNode = structures.TreeNode

/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/

// 解法一, 直接传入需要的 slice 范围作为输入, 可以避免申请对应 inorder 索引的内存, 内存使用(leetcode test case) 4.7MB -> 4.3MB.
func buildTree(inorder []int, postorder []int) *TreeNode {
postorderLen := len(postorder)
if len(inorder) == 0 {
return nil
}
root := &TreeNode{Val: postorder[postorderLen-1]}
postorder = postorder[:postorderLen-1]
for pos, node := range inorder {
if node == root.Val {
root.Left = buildTree(inorder[:pos], postorder[:len(inorder[:pos])])
root.Right = buildTree(inorder[pos+1:], postorder[len(inorder[:pos]):])
}
}
return root
}

// 解法二
func buildTree1(inorder []int, postorder []int) *TreeNode {
inPos := make(map[int]int)
for i := 0; i < len(inorder); i++ {
inPos[inorder[i]] = i
}
return buildInPos2TreeDFS(postorder, 0, len(postorder)-1, 0, inPos)
}

func buildInPos2TreeDFS(post []int, postStart int, postEnd int, inStart int, inPos map[int]int) *TreeNode {
if postStart > postEnd {
return nil
}
root := &TreeNode{Val: post[postEnd]}
rootIdx := inPos[post[postEnd]]
leftLen := rootIdx - inStart
root.Left = buildInPos2TreeDFS(post, postStart, postStart+leftLen-1, inStart, inPos)
root.Right = buildInPos2TreeDFS(post, postStart+leftLen, postEnd-1, rootIdx+1, inPos)
return root
}

``````

Apr 8, 2023