《剑指offer》的Go实现 面试题06：重建二叉树

题目：输入某二叉树的前序遍历和中序遍历的结果（切片），需要重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
前序遍历序列切片：{1, 2, 4, 7, 3, 5, 6, 8}
中序遍历序列切片：{4, 7, 2, 1, 5, 3, 8, 6}

代码：

package main

import "fmt"

type binaryTreeNode struct {
    Value int
    Left  *binaryTreeNode
    Right *binaryTreeNode
}

func (root *binaryTreeNode) preorderTraversal() {
    if root == nil {
        return
    }
    fmt.Printf("%d\t", root.Value)
    if root.Left != nil {
        root.Left.preorderTraversal()
    }
    if root.Right != nil {
        root.Right.preorderTraversal()
    }
}

func (root *binaryTreeNode) inorderTraversal() {
    if root == nil {
        return
    }
    if root.Left != nil {
        root.Left.inorderTraversal()
    }
    fmt.Printf("%d\t", root.Value)
    if root.Right != nil {
        root.Right.inorderTraversal()
    }
}

func construct(preorderSlice []int, inorderSlice []int) (root *binaryTreeNode) {
    if len(preorderSlice) == 0 || len(inorderSlice) == 0 {
        return
    }
    v, i := preorderSlice[0], 0
    for ; inorderSlice[i] != v; i++ {
    }
    root = &binaryTreeNode{Value:v}
    root.Left = construct(preorderSlice[1:i+1], inorderSlice[:i])
    root.Right = construct(preorderSlice[i+1:], inorderSlice[i+1:])
    return
}

func main() {
    preorderSlice := []int{1, 2, 4, 7, 3, 5, 6, 8}
    inorderSlice := []int{4, 7, 2, 1, 5, 3, 8, 6}
    root := construct(preorderSlice, inorderSlice)
    root.preorderTraversal()
    fmt.Println()
    root.inorderTraversal()
}

输出：

1   2   4   7   3   5   6   8   
4   7   2   1   5   3   8   6