剑指 07. 重建二叉树 👌

剑指 Offer 07. 重建二叉树

和力扣 105. 从前序与中序遍历序列构造二叉树一致

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

示例 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

//递归法，时空都是On
func buildTree(preorder []int, inorder []int) *TreeNode {
    if len(preorder) == 0 || len(inorder) == 0 {
        return nil
    }
    root := &TreeNode{preorder[0], nil, nil}        //1，根据前序，找到根节点，化为三部分
    i := 0
    for i = 0; i < len(inorder); i++ {
        if inorder[i] == preorder[0] {              //2，中序遍历，找到每层的root
            break 
        }
    }
    root.Left = buildTree(preorder[1: len(inorder[: i]) + 1], inorder[: i])
    root.Right = buildTree(preorder[len(inorder[: i]) +1 : ], inorder[i+1: ])
    return root
}