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. 前序：root-left-right 中序：left-root-right 后序：left-right-root
  2. 找到根节点
  3. 根据根节点在中序遍历中，左边为左子树，右边为右子树
  4. 递归构造子树
 type TreeNode struct {
      Val   int
      Left  *TreeNode
      Right *TreeNode
 }

func buildTree(preorder []int, inorder []int) *TreeNode {
     var root *TreeNode
     if len(preorder) == 0 || len(inorder) == 0 {
          return nil
     }
     ans := preorder[0]
     root = &TreeNode{Val: ans}
     
	  var idx int
	  for i, v := range inorder {
	  	if v == ans {
	  		idx = i
	  		break
	  	}
	  }
      
	  // 左开右闭
	  root.Left = buildTree(preorder[1:1+idx], inorder[:idx])
	  root.Right = buildTree(preorder[1+idx:], inorder[idx+1:])
      
	  return root
}