这是树的第9篇算法，力扣链接。
给定两个整数数组
preorder和inorder，其中preorder是二叉树的先序遍历，inorder是同一棵树的中序遍历，请构造二叉树并返回其根节点。示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 输出: [3,9,20,null,null,15,7]
先回忆一下前序遍历和中序遍历的定义：
中序遍历 (Inorder Traversal)
在中序遍历中，我们按照以下顺序遍历树中的节点：
- 遍历左子树
- 访问根节点
- 遍历右子树
对于二叉搜索树（BST），中序遍历会按照升序访问所有节点，因为二叉搜索树的特点是左子节点的值小于根节点的值，根节点的值小于右子节点的值。
前序遍历 (Preorder Traversal)
在前序遍历中，节点的访问顺序如下：
- 访问根节点
- 遍历左子树
- 遍历右子树
前序遍历通常用于创建树的副本。当你访问节点之后立即复制节点，你可以通过前序遍历复制所有节点并创建一棵相同的树。
假设有一棵二叉树如下：
A / \ B C / \ \ D E F对这棵树进行不同的遍历会得到以下结果：
- 中序遍历：
D, B, E, A, C, F。首先遍历左子树（D, B, E），然后是根节点（A），最后是右子树（C, F）。- 前序遍历：
A, B, D, E, C, F。首先访问根节点（A），然后是左子树（B, D, E），最后是右子树（C, F）。
因此我们可以根据先序遍历找到根节点即preorder[0]。我们可以根据中序遍历根节点的位置来判断出左右子树的节点数，同理，我们可以利用这个规则去每一个子树递归。
func buildTree(preorder []int, inorder []int) *TreeNode {
if len(preorder) == 0 {
return nil
}
index := 0
for ; index < len(inorder); index++ {
if preorder[0] == inorder[index] {
break
}
}
result := &TreeNode{Val: preorder[0]}
result.Left = buildTree(preorder[1:len(inorder[:index])+1], inorder[:index])
result.Right = buildTree(preorder[len(inorder[:index])+1:], inorder[index+1:])
return result
}这道题不是标准二叉树，不用纠结左右树的大小，如果判断大小就成小丑了。
这道题纯粹的是利用前序遍历和中序遍历构建树，迭代方法的逻辑如下：
遍历前序节点押入栈中，如果前序遍历的节点不等于中序遍历的节点就代表没有达到左子叶，继续押入栈，如果等就弹出，开始构建右子叶。
func buildTree(preorder []int, inorder []int) *TreeNode {
if len(preorder) == 0 {
return nil
}
result := &TreeNode{Val: preorder[0]}
stack := []*TreeNode{result}
var inorderIndex int
for i := 1; i < len(preorder); i++ {
node := stack[len(stack)-1]
if node.Val != inorder[inorderIndex] {
node.Left = &TreeNode{Val: preorder[i]}
stack = append(stack, node.Left)
} else {
for len(stack) != 0 && stack[len(stack)-1].Val == inorder[inorderIndex] {
node = stack[len(stack)-1]
stack = stack[:len(stack)-1]
inorderIndex++
}
node.Right = &TreeNode{Val: preorder[i]}
stack = append(stack, node.Right)
}
}
return result
}
