题目:
给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。
思路:
框架和105类似,从前序与中序遍历序列构造二叉树
leftsize=index-inStart 与105一致
注意后序左子树为 postStart 到 postStart+leftsize -1
右子树为 postStart+leftsize 到 postEnd -1 ;
class Solution {
HashMap<Integer,Integer> h=new HashMap<>();
public TreeNode buildTree(int[] inorder, int[] postorder) {
for(int i=0;i<inorder.length;i++){
h.put(inorder[i],i);
}
return con( inorder,0,inorder.length-1,
postorder,0,postorder.length-1);
}
private TreeNode con(int[] inorder,int inStart,int inEnd,
int[] postorder,int postStart,int postEnd){
// 终止条件
if(inStart>inEnd){
return null;
}
//找root
int rootVal=postorder[postEnd];
int index=h.get(rootVal);
TreeNode root=new TreeNode(rootVal);
// leftsize !!!
int leftsize=index-inStart;
root.left=con(inorder,inStart,index-1,
postorder,postStart,postStart+leftsize-1);
root.right=con(inorder,index+1,inEnd,
postorder,postStart+leftsize,postEnd-1); // 四行刚好各有一个+1/-1
return root;
}
}
构建子树的四行刚好各有一个+1/-1 !
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之家整理,本文链接:https://www.bmabk.com/index.php/post/89320.html