面试题07. 重建二叉树

面试题07. 重建二叉树

问题就是查找前序遍历和中序遍历中根节点，左节点，右节点 三者之前的界限，这个自己动手比划一下 ，例如就三个数 前序【3,9,20】 中序【9，3，20】，不然递归非让脑子浆糊了。
1前序遍历是 1根节点 2 左节点 3 右节点
2中序遍历是 1左节点 2根节点 3右节点
3根据前序遍历可以确定根节点是前序数组的第一个数preorder[0]
4 查找中序遍历左右节点的边界，中序遍历根节点的位置inorder[1] ，可以发现 inorder[1]左边都是树左节点的，左节点个数是1个，即[9]，inorder[1]右边都是树右节点的，右节点的个数3，即[15,20,7]，
5 查找前序遍历左右节点的边界，前序遍历第一个节点是根节点，依次是左节点和右节点，而我们中序遍历已经知道左节点的个数和右节点个数，所以preorder[1:1+1]即[9] ,而preorder[1+1:]就是右节点。
6 总结 边界索引里的中序遍历的根节点位置，即是表示出了根节点索引也是左节点的个数。

package main
import "fmt"
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}
func buildTree(preorder []int, inorder []int) *TreeNode {
    if len(preorder) == 0 {
        return nil
    }
    rootIdx := 0
    for i := range inorder {
        if inorder[i] == preorder[0] {
            rootIdx = i
            break
        }
    }
    root := &TreeNode{Val: preorder[0]}
    root.Left = buildTree(preorder[1:rootIdx+1], inorder[:rootIdx])
    root.Right = buildTree(preorder[rootIdx+1:], inorder[rootIdx+1:])
    return root
}
func printTree(root *TreeNode) {
    if root == nil {
        return
    }
    fmt.Println(root.Val)
    printTree(root.Left)
    printTree(root.Right)
}
func main() {
    r := buildTree([]int{3, 9, 20, 15, 7}, []int{9, 3, 15, 20, 7})
    printTree(r)
}