LeetCode 105
题目:
前序遍历: 根左右
中序遍历: 左根右
后序遍历: 左右根
思路:
构造二叉树,首先构造根节点,再构造左右子树
根节点即 前序遍历时的首结点 !
关键在于如何使用根节点将preorder和inorder划分为两部分,以此构造左右子树??
记结论:
找到根节点在中序遍历中的索引 index
左子树长度 leftsize=index-inStart !
前序左范围= prestart +1 到 prestart+leftsize (首结点为根节点,要排除!)
前序右范围=prestart+leftsize+1 到 preEnd
递归三步曲:
- 参数为前序、中序数组以及起点终点
- 终止条件:preStart > preEnd 则 return null
- 单层逻辑:构造首结点,再递归遍历构造左右子树
在找rootVal的索引时,可以用for遍历中序数组,但用HashMap可以减少时间复杂度
核心代码模式:
class Solution {
HashMap<Integer,Integer> h=new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
for(int i=0;i<preorder.length;i++){ key是值,value是索引
h.put(inorder[i],i);
}
return con(preorder,0,preorder.length-1,
inorder,0,inorder.length-1); //length 要减 1
}
private TreeNode con(int[] preorder,int preStart, int preEnd,
int[] inorder,int inStart,int inEnd){
if(preStart>preEnd){ // 这里用 (inStart>inEnd) 也可以
return null;
}
// 找root即前序nums[preStart],保留root在中序中的索引
int rootVal=preorder[preStart];
int index=h.get(rootVal);
int leftsize=index-inStart; // 用中序来求左子树的节点个数 ※※※
// 构造根节点
TreeNode root=new TreeNode(rootVal);
// 构造左右子树
root.left=con(preorder,preStart+1,preStart+leftsize, //preorder要除去根节点!!!
inorder,inStart,index-1);
root.right=con(preorder,preStart+leftsize+1,preEnd,
inorder,index+1,inEnd);
return root;
}
}
注意:
- preorder的子树范围要除去根节点!
- 构建子树的四行刚好各有一个+1/-1 !
- basecase 是
if(preStart>preEnd)
!
ACM 模式:
需要构建一个TreeNode 内部类、和遍历二叉树的方法;
输入不止一对数据;
每次的HashMap存有不同的中序数据,所以每个while当中新建一个HashMap,并传入con 函数中;
public class Main{
static class TreeNode{ // TreeNode 内部类
TreeNode left;
TreeNode right;
char val;
public TreeNode(char val){
this.val=val;
}
}
public static void main(String[] args){
Scanner In=new Scanner(System.in);
while(In.hasNext()){
HashMap<Character,Integer> h=new HashMap<>();
char[] pre=In.nextLine().toCharArray(); //前序
char[] in=In.nextLine().toCharArray(); //中序
for(int i=0;i<in.length;i++){
h.put(in[i],i);
}
TreeNode root=con(pre,0,pre.length-1, in,0,in.length-1 ,h);
StringBuffer s=new StringBuffer();
back(root,s); // 后序遍历
System.out.println(s);
}
}
static TreeNode con(char[] pre,int preStart,int preEnd,
char[] in,int inStart,int inEnd,
HashMap<Character,Integer> h){ // 构建二叉树
if(preStart>preEnd){
return null;
}
char val=pre[preStart];
int index=h.get(val);
int leftsize=index-inStart;
TreeNode root=new TreeNode(val);
root.left=con(pre,preStart+1,preStart+leftsize,
in,inStart,index-1,h);
root.right=con(pre,preStart+leftsize+1,preEnd,
in,index+1,inEnd,h);
return root;
}
static void back(TreeNode root,StringBuffer s){ // 后序遍历
if(root==null){
return ;
}
// 后序
back(root.left,s);
back(root.right,s);
s.append(root.val);
}
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/89321.html