代码随想录二叉树——从中序与后序遍历序列构造二叉树
题目
根据一棵树的中序遍历与后序遍历构造二叉树。
注意: 你可以假设树中没有重复的元素。
例如，给出
中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3] 返回如下的二叉树：
思路
以后序数组的最后一个元素（因为后序遍历是左右中，最后一个元素为根节点）为切割点，先切中序数组（因为中序比那里是左中右，可以根据根节点分出左右子树），根据中序数组，反过来再切后序数组（继续找新的根节点，然后继续切下去）。一层一层切下去，每次后序数组最后一个元素就是节点元素。
采用递归法
- 如果数组大小为0，说明是空节点
- 如果不为空，则选取最后一个元素（根节点）
- 在中序数组中找到这个根节点的位置
- 切割中序数组，切成中序左数组和中序右数组
- 切割后序数组，切成后序左数组和后序右数组
- 递归处理左区间和右区间
注：切割过程中保持循环不变量 （这里保持左闭右开）
java代码如下：
class Solution {
Map<Integer,Integer> map;//根据数值查位置
public TreeNode buildTree(int[] inorder,int[] postorder){
map =new HahMap<>();
for(int i= 0; i< inorder.length; i++){
map.put(inorder[i],i);//用map保存中序序列的数值对应的下标位置i
}
return findNode(inorder, 0, inorder.length,postprder, 0, postorder.length);//左闭右开
}
public TreeNode findNode(int[] inorder,int inBegin,int inEnd,int[] postorder,int postBegin,int postEnd){
if(inBegin >= inEnd || postBegin >= psotEnd){//不满足左闭右开，说明没有元素，返回空树
return null;
}
int rootIndex = map.get(postorder[pestEnd-1]);//找到后序遍历的最后一个元素在中序遍历中的位置
TreeNode root = new TreeNode(inorder[rootIndex]);//构造节点，存放根节点值
int lenOfLeft = rootIndex- inBegin;//确定中序左子树的长度，用来确定切割后序左子树的长度（因为中序左数组长度和后序左子树长度相等）
root.left = find(inorder, inBegin, rootIndex , postorder, postBegin, postBegin + lenOfLeft);
root.right = findNode(inorder, rootIndex + 1, inEnd,postorder, postBegin + lenOfLeft, postEnd - 1);
return root;
}
}