重建二叉树 Go实现
重建二叉树
热身
前序遍历 [ 根左右 ]
对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。
中序遍历 [ 左根右 ]
对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。
后序遍历 [ 左右根 ]
对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。
题目
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列 {1,2,4,7,3,5,6,8} 和中序遍历序列 {4,7,2,1,5,3,8,6} ，则重建二叉树并返回。
思路
用前序遍历找到根结点
用根结点在中序遍历中切开左右子树，递归重建二叉树
实现
package maintype TreeNode struct {Val intLeft *TreeNodeRight *TreeNode}func main() {var pre = []int{1, 2, 3, 4, 5, 6, 7}var vin = []int{3, 2, 4, 1, 6, 5, 7}reConstructBinaryTree(pre, vin)}func reConstructBinaryTree(pre []int, vin []int) *TreeNode {if len(pre) == 0 {return nil}// 找到根节点root_val := pre[0]root_node := &TreeNode{Val: root_val,}// 切开中序var index intfor index = range vin {if vin[index] == root_val {break}}// 大树拆小树递归处理root_node.Left = reConstructBinaryTree(pre[1:1+index], vin[:index])root_node.Right = reConstructBinaryTree(pre[1+index:], vin[index+1:])return root_node}