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

preorder 根 左 右
inorder  左 根 右
1.找到根的位置
2.递归构造左子树和右子树

func buildTree(preorder []int, inorder []int) *TreeNode {
  if len(preorder) == 0 {
    return nil
  }
  root := &TreeNode{
    Val:   preorder[0],
    Left:  nil,
    Right: nil,
  }
  i := 0
  for ; i < len(inorder); i++ {
    if inorder[i] == preorder[0] {
      break
    }
  }
  // preorder 根 左 右
  // inorder  左 根 右
  // 中序根==i
  leftStart := 1
  leftEnd := i + 1
  rightStart := i + 1
  root.Left = buildTree(preorder[leftStart:leftEnd], inorder[:i])
  root.Right = buildTree(preorder[rightStart:], inorder[i+1:])
  return root
}