Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit37c4105

Browse files
committed
merge
1 parentfa314c2 commit37c4105

File tree

2 files changed

+112
-41
lines changed

2 files changed

+112
-41
lines changed

‎sort/MergeSort.java

Lines changed: 0 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -72,33 +72,6 @@ private static int[] merge(int[] left, int[] right) {
7272
returnret;
7373
}
7474

75-
publicstaticvoidmergeSort2(int[]data) {
76-
// parameter valid judge.
77-
if (data ==null) {
78-
returnnull;
79-
}
80-
81-
// the base case.
82-
intlen =data.length;
83-
if (len <=1) {
84-
returndata;
85-
}
86-
87-
// divide into two arrays.
88-
// create left half and right half.
89-
intleft[] =newint[len/2];
90-
intright[] =newint[len -len/2];
91-
92-
System.arraycopy(data,0,left,0,len/2);
93-
System.arraycopy(data,len/2,right,0,len -len/2);
94-
95-
// call itself to sort left half
96-
left =mergeSort(left);
97-
right =mergeSort(right);
98-
99-
returnmerge(left,right);
100-
}
101-
10275
publicstaticvoidmain(String[]args) {
10376
int[]a =newint[SIZE];
10477
for (inti =0;i <SIZE;i++)

‎tree/TreeDemo.java

Lines changed: 112 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,9 @@
1-
@@ -1,1260 +0,0@@
21
packageAlgorithms.tree;
32

43
importjava.util.ArrayList;
54
importjava.util.Iterator;
65
importjava.util.LinkedList;
6+
importjava.util.List;
77
importjava.util.Queue;
88
importjava.util.Stack;
99

@@ -32,8 +32,8 @@
3232
* LAC 求解最小公共祖先, 使用list来存储path.
3333
* LCABstRec 递归求解BST树.
3434
* LCARec 递归算法 .
35-
*
3635
* 12. 求二叉树中节点的最大距离：getMaxDistanceRec
36+
*
3737
* 13. 由前序遍历序列和中序遍历序列重建二叉树：rebuildBinaryTreeRec
3838
* 14. 判断二叉树是不是完全二叉树：isCompleteBinaryTree, isCompleteBinaryTreeRec
3939
* 15. 找出二叉树中最长连续子串(即全部往左的连续节点，或是全部往右的连续节点）findLongest
@@ -98,6 +98,12 @@ public static void main(String[] args) {
9898

9999
TreeNodet7 =newTreeNode(0);
100100

101+
TreeNodet8 =newTreeNode(0);
102+
TreeNodet9 =newTreeNode(0);
103+
TreeNodet10 =newTreeNode(0);
104+
TreeNodet11 =newTreeNode(0);
105+
106+
101107
t1.left =t2;
102108
t1.right =t3;
103109
t2.left =t4;
@@ -106,6 +112,12 @@ public static void main(String[] args) {
106112

107113
t4.left =t7;
108114

115+
// test distance
116+
t5.right =t8;
117+
t8.right =t9;
118+
t9.right =t10;
119+
t10.right =t11;
120+
109121
/*
110122
10
111123
/ \
@@ -115,18 +127,20 @@ public static void main(String[] args) {
115127
/
116128
0
117129
*/
118-
System.out.println(LCABstRec(t1,t2,t4).val);
119-
System.out.println(LCABstRec(t1,t2,t6).val);
120-
System.out.println(LCABstRec(t1,t4,t6).val);
121-
System.out.println(LCABstRec(t1,t4,t7).val);
122-
System.out.println(LCABstRec(t1,t3,t6).val);
123-
124-
System.out.println(LCA(t1,t2,t4).val);
125-
System.out.println(LCA(t1,t2,t6).val);
126-
System.out.println(LCA(t1,t4,t6).val);
127-
System.out.println(LCA(t1,t4,t7).val);
128-
System.out.println(LCA(t1,t3,t6).val);
129-
System.out.println(LCA(t1,t6,t6).val);
130+
// System.out.println(LCABstRec(t1, t2, t4).val);
131+
// System.out.println(LCABstRec(t1, t2, t6).val);
132+
// System.out.println(LCABstRec(t1, t4, t6).val);
133+
// System.out.println(LCABstRec(t1, t4, t7).val);
134+
// System.out.println(LCABstRec(t1, t3, t6).val);
135+
//
136+
// System.out.println(LCA(t1, t2, t4).val);
137+
// System.out.println(LCA(t1, t2, t6).val);
138+
// System.out.println(LCA(t1, t4, t6).val);
139+
// System.out.println(LCA(t1, t4, t7).val);
140+
// System.out.println(LCA(t1, t3, t6).val);
141+
// System.out.println(LCA(t1, t6, t6).val);
142+
143+
System.out.println(getMaxDistanceRec(t1));
130144

131145
//System.out.println(isSame(r1, t1));
132146

@@ -1185,6 +1199,90 @@ public static boolean LCAPath(TreeNode root, TreeNode node, ArrayList<TreeNode>
11851199
// found
11861200
returntrue;
11871201
}
1202+
1203+
/*
1204+
* * 12. 求二叉树中节点的最大距离：getMaxDistanceRec
1205+
*
1206+
* 首先我们来定义这个距离：
1207+
* 距离定义为：两个节点间边的数目.
1208+
* 如：
1209+
* 1
1210+
* / \
1211+
* 2 3
1212+
* \
1213+
* 4
1214+
* 这里最大距离定义为2，4的距离，为3.
1215+
* 求二叉树中节点的最大距离 即二叉树中相距最远的两个节点之间的距离。 (distance / diameter)
1216+
* 递归解法：
1217+
* 返回值设计：
1218+
* 返回1. 深度， 2. 当前树的最长距离
1219+
* (1) 计算左子树的深度，右子树深度，左子树独立的链条长度，右子树独立的链条长度
1220+
* (2) 最大长度为三者之最：
1221+
* a. 通过根节点的链，为左右深度+2
1222+
* b. 左子树独立链
1223+
* c. 右子树独立链。
1224+
*
1225+
* (3)递归初始条件：
1226+
* 当root == null, depth = -1.maxDistance = -1;
1227+
*
1228+
*/
1229+
publicstaticintgetMaxDistanceRec(TreeNoderoot) {
1230+
returngetMaxDistanceRecHelp(root).maxDistance;
1231+
}
1232+
1233+
publicstaticResultgetMaxDistanceRecHelp(TreeNoderoot) {
1234+
Resultret =newResult(-1, -1);
1235+
1236+
if (root ==null) {
1237+
returnret;
1238+
}
1239+
1240+
Resultleft =getMaxDistanceRecHelp(root.left);
1241+
Resultright =getMaxDistanceRecHelp(root.right);
1242+
1243+
// 深度应加1， the depth from the subtree to the root.
1244+
ret.depth =Math.max(left.depth,right.depth) +1;
1245+
1246+
// 左子树，右子树与根的距离都要加1，所以通过根节点的路径为两边深度+2
1247+
intcrossLen =left.depth +right.depth +2;
1248+
1249+
// 求出cross根的路径，及左右子树的独立路径，这三者路径的最大值。
1250+
ret.maxDistance =Math.max(left.maxDistance,right.maxDistance);
1251+
ret.maxDistance =Math.max(ret.maxDistance,crossLen);
1252+
1253+
returnret;
1254+
}
1255+
1256+
1257+
privatestaticclassResult {
1258+
intdepth;
1259+
intmaxDistance;
1260+
publicResult(intdepth,intmaxDistance) {
1261+
this.depth =depth;
1262+
this.maxDistance =maxDistance;
1263+
}
1264+
}
1265+
1266+
/*
1267+
* 13. 由前序遍历序列和中序遍历序列重建二叉树：rebuildBinaryTreeRec
1268+
* */
1269+
publicstaticTreeNoderebuildBinaryTreeRec(List<Integer>preOrder,List<Integer>inOrder) {
1270+
if (preOrder ==null ||inOrder ==null) {
1271+
returnnull;
1272+
}
1273+
1274+
// If the traversal is empty, just return a NULL.
1275+
if (preOrder.size() ==0 ||inOrder.size() ==0) {
1276+
returnnull;
1277+
}
1278+
1279+
// we can get the root from the preOrder. Because the first one is the
1280+
// root.
1281+
TreeNoderoot =preOrder.get(0);
1282+
1283+
returnnull;
1284+
1285+
}
11881286

11891287
/*
11901288
* 15. findLongest

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp