输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/
9 20
/
15 7
限制：
0 <= 节点个数 <= 5000
题目分析：
提到树相关的题目，我们首先想到递归，递归相关的问题，我们可以考虑借助栈来实现迭代解决。本题，有两种解法。
1，递归法：
前序遍历的形式总是
[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]
即根节点总是前序遍历中的第一个节点。而中序遍历的形式总是
[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]
因此，我们可以从根节点切分开来，剩下的两部分分别对应左子树和右子树，递归解决即可
代码语言：javascript复制/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func buildTree(preorder []int, inorder []int) *TreeNode {
if len(preorder)<1{
return nil
}
root:=preorder[0]
i:=0
for i<len(inorder)&& inorder[i]!=root{
i
}
Left:=buildTree(preorder[1:i 1],inorder[:i])
Right:=buildTree(preorder[i 1:],inorder[i 1:])
return &TreeNode{
Val:root,
Left:Left,
Right:Right,
}
}2，迭代法
前序遍历的过程是这样的：
（1）我们从根节点开始，一直遍历左孩子，直到没有左孩子为止。什么时候没有左孩子呢，我们遇到了中序遍历的第一个节点。
我们可以将上述过程，通过遍历前缀树，建树过程来实现。
（2）没有左孩子后，我们需要回溯，直到遇到右孩子，怎么做才能回溯呢？我们需要把（1）过程中遍历的节点入栈，然后通过出栈来回溯。
（3）出栈的过程是怎么样的呢？我们同步出栈和右移中序遍历的指针，中序遍历值和栈顶相等说明，没有遇到右孩子。遇到右孩子后，我们重复执行步骤（1）
代码语言：javascript复制/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func buildTree(preorder []int, inorder []int) *TreeNode {
if len(preorder)<1{
return nil
}
root:=&TreeNode{
Val:preorder[0],
}
stack:=[]*TreeNode{root}
index:=0
for i:=1;i<len(preorder);i {
node:=stack[len(stack)-1]
if node.Val!=inorder[index]{
l:=&TreeNode{Val:preorder[i]}
node.Left=l
stack=append(stack,l)
}else{
for len(stack) != 0 && stack[len(stack)-1].Val == inorder[index] {
node = stack[len(stack)-1]
stack = stack[:len(stack)-1]
index
}
node.Right = &TreeNode{Val:preorder[i]}
stack = append(stack, node.Right)
}
}
return root
}
