7.md

重建二叉树

热身

前序遍历 [ 根左右 ]

• 对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。

中序遍历 [ 左根右 ]

• 对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。

后序遍历 [ 左右根 ]

• 对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。

题目

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

思路

• 用前序遍历找到根结点
• 用根结点在中序遍历中切开左右子树，递归重建二叉树

实现

package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *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 int
	for 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
}