-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathreConstructBinaryTree.java
More file actions
114 lines (112 loc) · 3.51 KB
/
reConstructBinaryTree.java
File metadata and controls
114 lines (112 loc) · 3.51 KB
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
//重建二叉树，最重要是找到根节点，然后找其左子树和右子树
import java.util.Map;
import java.util.HashMap;
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if(pre==null||in ==null)
return null;
Map<Integer,Integer> map=new HashMap<Integer,Integer>();//利用了map的get方法可以找到根节点的index，然后再进行递归
for(int i=0;i<in.length;i++)
map.put(in[i],i);
return preIn(pre,0,pre.length-1,in,0,in.length-1,map);
}
public TreeNode preIn(int [] pre,int pi,int pend,int [] in,int ni,int nend,Map<Integer,Integer> map)
{
if(pi>pend)
return null;
TreeNode head = new TreeNode(pre[pi]);
int index=map.get(pre[pi]);
head.left=preIn(pre,pi+1,index+pi-ni,in,ni,index-1,map);
head.right=preIn(pre,index+pi-ni+1,pend,in,index+1,nend,map);
return head;
}
}
/* 先序遍历第一个位置肯定是根节点node，
中序遍历的根节点位置在中间p，在p左边的肯定是node的左子树的中序数组，p右边的肯定是node的右子树的中序数组
另一方面，先序遍历的第二个位置到p，也是node左子树的先序子数组，剩下p右边的就是node的右子树的先序子数组 把四个数组找出来，分左右递归调用即可 */
class Solution {
public:
struct TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> in) {
int inlen=in.size();
if(inlen==0)
return NULL;
vector<int> left_pre,right_pre,left_in,right_in;
//创建根节点，根节点肯定是前序遍历的第一个数
TreeNode* head=new TreeNode(pre[0]);
//找到中序遍历根节点所在位置,存放于变量gen中
int gen=0;
for(int i=0;i<inlen;i++)
{
if (in[i]==pre[0])
{
gen=i;
break;
}
}
//对于中序遍历，根节点左边的节点位于二叉树的左边，根节点右边的节点位于二叉树的右边
//利用上述这点，对二叉树节点进行归并
for(int i=0;i<gen;i++)
{
left_in.push_back(in[i]);
left_pre.push_back(pre[i+1]);//前序第一个为根节点
}
for(int i=gen+1;i<inlen;i++)
{
right_in.push_back(in[i]);
right_pre.push_back(pre[i]);
}
//和shell排序的思想类似，取出前序和中序遍历根节点左边和右边的子树
//递归，再对其进行上述所有步骤，即再区分子树的左、右子子数，直到叶节点
head->left=reConstructBinaryTree(left_pre,left_in);
head->right=reConstructBinaryTree(right_pre,right_in);
return head;
}
};
*/