📑 题目：106. 从中序与后序遍历序列构造二叉树

🚀 本题 LeetCode 传送门

题目大意

根据一棵树的中序遍历与后序遍历构造二叉树。

注意: 你可以假设树中没有重复的元素。

解题思路

• 给出 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
}