题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
牛客网在线测试
解题思路
解决这个题的关键是要清楚前序遍历序列和中序遍历序列的特点。
前序遍历序列的结构是这个样子的(根节点，左子树的节点...,右子树的节点...)
而中序遍历序列的结构是这个样子的(左子树的节点...,根节点,右子树的节点...)
根据遍历序列的特点，我们可以通过先序遍历序列找到根节点的值，然后根据根节点的值，再利用中序遍历的值，可以拿到左右子树的节点值。
解题代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
private Map<Integer,Integer> indexOfInOrders=new HashMap<Integer, Integer>();
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
for(int i=0;i<in.length;i++){
indexOfInOrders.put(in[i],i);
}
return reConstructBinaryTree(pre,0,pre.length-1,0);
}
private TreeNode reConstructBinaryTree(int[] pre,int preL,int preR,int inL){
if(preL>preR){
return null;
}
TreeNode root=new TreeNode(pre[preL]);
int inIndex = indexOfInOrders.get(root.val);
int leftTreeSize=inIndex-inL;
root.left=reConstructBinaryTree(pre,preL+1,preL+leftTreeSize,inL);
root.right=reConstructBinaryTree(pre,preL+leftTreeSize+1,preR,inL+leftTreeSize+1);
return root;
}
|