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

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

提示:

• 1 <= preorder.length <= 3000
• inorder.length == preorder.length
• -3000 <= preorder[i], inorder[i] <= 3000
• preorder 和 inorder 均 无重复 元素
• inorder 均出现在 preorder
• preorder 保证 为二叉树的前序遍历序列
• inorder 保证 为二叉树的中序遍历序列

题解：

递归法：

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