重建二叉树(Golang)《剑指offer》

题目描述：

输入某个二叉树的前序遍历和中序遍历的结果，请重建该二叉树。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如：输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建如图所示的二叉树并输出它的头节点。

主要代码如下：

type BinaryTreeNode struct {
	Value     int
	LeftNode  *BinaryTreeNode
	RightNode *BinaryTreeNode
}

func NewBinaryTreeNode(value int) *BinaryTreeNode {
	return &BinaryTreeNode{Value: value}
}

func CreateTreeConstruct(preorder []int, inorder []int) *BinaryTreeNode {
	if preorder == nil || inorder == nil {
		return nil
	}
	return createTreeConstruct(preorder, 0, len(preorder)-1, inorder, 0, len(inorder)-1)
}

// 参数：前序遍历数组，前序起始位置，中序遍历数组，中序起始位置
func createTreeConstruct(preorder []int, preStart int, preEnd int, inorder []int, inStart int, inEnd int) *BinaryTreeNode {
	if preStart > preEnd || inStart > inEnd {
		return nil
	}
	// 前序遍历序列的第一个数字是根节点的值
	root := NewBinaryTreeNode(preorder[preStart])
	// 找到中序遍历数组中根节点的位置
	var rootIndex int
	for i := 0; i < len(inorder); i++ {
		if inorder[i] == root.Value {
			rootIndex = i
			break
		}
	}
	// 计算左子树和右子树的节点数
	leftCount := rootIndex - inStart
	//rightCount := inEnd - rootIndex

	// 左子树递归
	root.LeftNode = createTreeConstruct(preorder, preStart+1, preStart+leftCount, inorder, inStart, rootIndex-1)
	root.RightNode = createTreeConstruct(preorder, preStart+leftCount+1, preEnd, inorder, rootIndex+1, inEnd)
	return root
}

// 前序遍历
func printPreOrder(root *BinaryTreeNode, order []int) []int {
	if root == nil {
		return nil
	}
	order = append(order, root.Value)
	if root.LeftNode != nil {
		order = printPreOrder(root.LeftNode, order)
	}
	if root.RightNode != nil {
		order = printPreOrder(root.RightNode, order)
	}
	return order
}

// 中序遍历
func printInOrder(root *BinaryTreeNode, order []int) []int {
	if root == nil {
		return nil
	}
	if root.LeftNode != nil {
		order = printInOrder(root.LeftNode, order)
	}
	order = append(order, root.Value)
	if root.RightNode != nil {
		order = printInOrder(root.RightNode, order)
	}
	return order
}

写完代码之后又写了前序遍历和中序遍历自己测试了一下，结果是对的。分析过程就不写了，那本书上写的很详细，如果还是不懂的可以评论联系我。

说明：前序遍历的数组中第一个位置是根节点，中序遍历数组中根节点的左边第左子树，右边是右子树。