从前序和中序序列构造二叉树

问题陈述

由中序序列和前序序列构造二叉树。

问题求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class PI_BuildTree {
public TreeNode buildTree(int[] preOrder,int[] inOrder){
return buildHelper(preOrder,0,preOrder.length,inOrder,0,inOrder.length);
}
public TreeNode buildHelper(int[] preOrder,int p_start,int p_end,int[] inOrder,int i_start,int i_end){
if(p_start==p_end) return null;
int root_val=preOrder[0];
TreeNode root=new TreeNode(root_val);
//在中序中找到根结点位置
int i_root_index=0;
for(int i=i_start;i<i_end;i++){
if(inOrder[i]==root_val){
i_root_index=i;
break;
}
}
int leftNum=i_root_val-i_start;
root.left=buildHelper(preOrder,p_start+1,p_start+leftNum+1,inOrder,i_start,i_root_index);
root.right=buildHelper(inOrder,p_start+leftNum+1,p_end,inOrder,i_root_index+1,i_end);
return root;
}
public static void main(String[] args){
int[] preOrder={3,9,20,15,7};
int[] inOrder={9,3,15,20,7};
PI_BuildTree pi_buildTree=new PI_BuildTree();
pi_buildTree.buildTree(preOrder,inOrder);
}
}

上边的代码很好理解,但存在一个问题,在中序遍历中找到根节点的位置每次都得遍历中序遍历的数组去寻找,参考这里 ,我们可以用一个HashMap把中序遍历数组的每个元素的值和下标存起来,这样寻找根节点的位置就可以直接得到了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution{
public TreeNode buildTree(int[] preorder,int[] inorder){
//把中序序列存入一个HashMap
HashMap<Integer,Integer> map=new HashMap<>();
for(int i=0;i<inorder.length;i++){
map.put(inorder[i],i);
}
return buildTreeHelper(preorder,0,preorder.length,inorder,0,inorder.length,map);
}
public TreeNode buildTreeHelper(int[] preorder,int p_start,int p_end,int[] inorder,int i_start,int i_end,HashMap<Integer,Integer> map){
if(p_start==p_end) return null;

int root_val=preorder[p_start];
TreeNode root=new TreeNode(root_val);
//获取根结点在中序中的索引
int i_root_index=map.get(root_val);
int leftnum=i_root_index-i_start;
root.left=buildTreeHelper(preorder,p_start+1,p_start+1+leftnum,inorder,i_start,i_root_index,map);
root.right=buildTreeHelper(preorder,p_start+1+leftnum,p_end,inorder,i_root_index+1,i_end,map);
return root;
}
}