106. 从中序与后序遍历序列构造二叉树

题目描述：

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

示例 1：

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]

示例 2：

输入：inorder = [-1], postorder = [-1]
输出：[-1]

提示：

• 1 <= inorder.length <= 3000
• postorder.length == inorder.length
• -3000 <= inorder[i], postorder[i] <= 3000
• inorder 和 postorder 都由 不同 的值组成
• postorder 中每一个值都在 inorder 中
• inorder 保证是树的中序遍历
• postorder 保证是树的后序遍历

---

解题分析及思路：

这道题考察的是二叉树的遍历，不熟悉二叉树的遍历可以查看二叉树。

题目给出的是中序遍历和后序遍历后的结果，由此重新生成原有的二叉树。

将一棵二叉树分别进行中序遍历和后序遍历：

• 针对中序遍历后的结果，可以分析出结果的构成为[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]
• 针对后序遍历后的结果，可以分析出结果的构成为[ [左子树的前序遍历结果], [右子树的前序遍历结果], 根节点 ]

而我们仅仅只需要根据后序遍历的最后一个值，也就是根节点的值，即可定位到中序遍历根节点的位置。

随后根据中序遍历根节点的位置，可以将所有的数据划分为根节点的左右子树。

最后采取同样的方式（递归解决）分别定位左右子树的值及其子树。

其中，定位到根节点在中序遍历的下标为index:

• 左子树的的中序遍历集合为inorder[:index]，左子树的后序遍历集合为postorder[:len(inorder[:index])]
• 右子树的的中序遍历集合为inorder[index+1:]，右子树的后序遍历集合为postorder[len(inorder[:index]):len(inorder[:index])+len(inorder[index+1:])]

func buildTree(inorder []int, postorder []int) *TreeNode {
	if len(postorder) == 0 {
		return nil
	}
	root := &TreeNode{Val: postorder[len(postorder)-1]}
	var index int
	for index = range inorder {
		if inorder[index] == postorder[len(postorder)-1] {
			break
		}
	}
	root.Left = buildTree(inorder[:index], postorder[:len(inorder[:index])])
	root.Right = buildTree(inorder[index+1:], postorder[len(inorder[:index]):len(inorder[:index])+len(inorder[index+1:])])
	return root
}

复杂度：

• 时间复杂度：O(N)，其中 N 是树中的节点个数.
• 空间复杂度：O(1)，只使用常数额外空间。

执行结果：

• 执行耗时:6 ms,击败了26.59% 的Go用户
• 内存消耗:3.6 MB,击败了93.35% 的Go用户