题目要求:给定一颗二叉树的中序遍历的数组inorder[]和后序遍历的数组postorder[],构造出这颗二叉树。
我们知道,根据前序+中序 或者 后序+中序都可以构造出一颗二叉树,而前序+后序则不能构造出一颗二叉树。
例如,下图的二叉树的
前序序列为:1-3-5-6
中序序列为:3-1-6-5
后序序列为:3-6-5-1
一颗二叉树
那么为什么前序+中序或者后序+中序行,而前序+后序不行呢?
(2)后序+中序的构造过程:
后序序列为:3-6-5-1
中序序列为:3-1-6-5
后序序列是先左,再右,再根的过程。那么前序中的最后一个数1一定为二叉树的根,根据这个1我们可以去中序序列中找1所在的位置,然后因为中序序列是先左再根再右的过程,那么中序序列的1的左边部分(3)一定是左子树的节点,1的右边部分(6和5)一定是右子树的节点,根据这个结果,我们再去后序序列中找根的左子树部分……我们发现这是个递归的过程。
直到当前子树的根节点没有左右节点为止,这样,一颗二叉树一定可以被构造出来。
根据这个过程,我们得到了这道题目的解题思路。
需要四个辅助的指针,一个postend指向当前先序序列中的开始位置(当前树的根节点),一个instart指向当前中序序列的开始位置,一个inend指向当前中序序列的结束位置,一个inIndex指向当前中序序列中的根的位置。
代码如下。
返回结果为