- [LeetCode OJ]-Construct Binary T
- [LeetCode OJ]- Construct Binary
- LeetCode-105-从前序与中序遍历序列构造二叉树
- 2019-06.23-2019.06.30
- LeetCode | 0105. Construct Binar
- Construct Binary Tree from Preor
- 2.Construct Binary Tree from Pre
- LeetCode | 0106. Construct Binar
- [LeetCode] Construct Binary Tree
- [LeetCode] Construct Binary Tree
题目要求：给定一颗二叉树的中序遍历的数组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指向当前中序序列中的根的位置。
代码如下。
返回结果为
网友评论