【力扣】106. 从中序与后序遍历序列构造二叉树

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

示例 1:

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]

示例 2:

输入：inorder = [-1], postorder = [-1]
输出：[-1]

提示:

• 1 <= inorder.length <= 3000
• postorder.length == inorder.length
• -3000 <= inorder[i], postorder[i] <= 3000
• inorder 和 postorder 都由 不同 的值组成
• postorder 中每一个值都在 inorder 中
• inorder 保证是树的中序遍历
• postorder 保证是树的后序遍历

题解：

递归法：

func buildTree(inorder []int, postorder []int) *TreeNode {
	// 初始化 hash 映射, 这个映射存储着中序遍历元素和它们对应的索引
	hash := make(map[int]int)
	for i := 0; i < len(inorder); i++ {
		hash[inorder[i]] = i
	}
	// 定义 helper 函数的原型，这是一个递归函数，用于构建二叉树
	var helper func(inorderStart, inorderEnd, postorderStart, postorderEnd int) *TreeNode
	// 实现 helper 函数, 它接受四个参数：
	// inorderStart, inorderEnd: 表示当前处理的子树在中序遍历数组中的起始和结束位置
	// postorderStart, postorderEnd: 表示当前处理的子树在后序遍历数组中的起始和结束位置
	helper = func(inorderStart, inorderEnd, postorderStart, postorderEnd int) *TreeNode {
		// 如果子树在中序或后序遍历中没有元素, 则返回 nil
		if inorderEnd < inorderStart || postorderEnd < postorderStart {
			return nil
		}
		// 后序遍历的最后一个元素是子树的根节点
		rootVal := postorder[postorderEnd]
		// 获取根节点在中序遍历中的位置
		rootIndex := hash[rootVal]
		// 返回新的树节点，这里递归构建了左子树和右子树
		return &TreeNode{
			Val:   rootVal,
			Left:  helper(inorderStart, rootIndex-1, postorderStart, postorderStart+rootIndex-inorderStart-1),
			Right: helper(rootIndex+1, inorderEnd, postorderStart+rootIndex-inorderStart, postorderEnd-1),
		}
	}
	return helper(0, len(inorder)-1, 0, len(postorder)-1)
}