Skip to content

Commit 9aef8fe

Browse files
dunwudunwu
committed
update codes and docs
1 parent d39b288 commit 9aef8fe

File tree

5 files changed

+263
-5
lines changed

5 files changed

+263
-5
lines changed

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/tree/TreeUtils.java‎

Lines changed: 75 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -2,10 +2,7 @@
22

33
import io.github.dunwu.algorithm.tree.btree.TreeNode;
44

5-
import java.util.ArrayList;
6-
import java.util.LinkedList;
7-
import java.util.List;
8-
import java.util.Queue;
5+
import java.util.*;
96

107
/**
118
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
@@ -99,6 +96,80 @@ public static List<TreeNode> levelTraverse(TreeNode root) {
9996
return list;
10097
}
10198

99+
public static String rserialize(TreeNode root, String str) {
100+
if (root == null) {
101+
str += "null,";
102+
} else {
103+
str += str.valueOf(root.val) + ",";
104+
str = rserialize(root.left, str);
105+
str = rserialize(root.right, str);
106+
}
107+
return str;
108+
}
109+
110+
public static String serialize(TreeNode root) {
111+
String text = rserialize(root, "");
112+
while (text.endsWith("null,")) {
113+
int index = text.lastIndexOf("null,");
114+
text = text.substring(0, index);
115+
}
116+
if (text.endsWith(",")) {
117+
text = text.substring(0, text.length() - 1);
118+
}
119+
return text;
120+
}
121+
122+
public static TreeNode rdeserialize(List<String> list) {
123+
List<TreeNode> nodes = new ArrayList<>();
124+
125+
for (String value : list) {
126+
// 创建结点，每一个结点的左结点和右结点为null
127+
TreeNode node;
128+
if (value == null || value.equalsIgnoreCase("null")) {
129+
node = null;
130+
} else {
131+
node = new TreeNode(Integer.parseInt(value), null, null);
132+
}
133+
// list中存着每一个结点
134+
nodes.add(node);
135+
}
136+
137+
// 构建二叉树
138+
if (nodes.size() > 0) {
139+
// i表示的是根节点的索引，从0开始
140+
for (int i = 0; i < list.size() / 2 - 1; i++) {
141+
if (nodes.get(2 * i + 1) != null) {
142+
// 左结点
143+
nodes.get(i).left = nodes.get(2 * i + 1);
144+
}
145+
if (nodes.get(2 * i + 2) != null) {
146+
// 右结点
147+
nodes.get(i).right = nodes.get(2 * i + 2);
148+
}
149+
}
150+
// 判断最后一个根结点：因为最后一个根结点可能没有右结点，所以单独拿出来处理
151+
int lastIndex = list.size() / 2 - 1;
152+
153+
// 左结点
154+
nodes.get(lastIndex).left = nodes.get(lastIndex * 2 + 1);
155+
// 右结点，如果数组的长度为奇数才有右结点
156+
if (list.size() % 2 == 1) {
157+
nodes.get(lastIndex).right = nodes.get(lastIndex * 2 + 2);
158+
}
159+
160+
return nodes.get(0);
161+
} else {
162+
return null;
163+
}
164+
}
165+
166+
public static TreeNode deserialize(String data) {
167+
data = data.substring(1, data.length() - 1);
168+
String[] nums = data.split(",");
169+
List<String> list = new LinkedList<>(Arrays.asList(nums));
170+
return rdeserialize(list);
171+
}
172+
102173
public static void main(String[] args) {
103174
Integer[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
104175
TreeNode head = TreeUtils.asTree(array);

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/tree/btree/二叉树的序列化与反序列化.java‎

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
package io.github.dunwu.algorithm.tree.btree;
2+
3+
import java.util.Arrays;
4+
import java.util.LinkedList;
5+
import java.util.List;
6+
7+
/**
8+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
9+
* @since 2020-07-06
10+
*/
11+
public class 二叉树的序列化与反序列化 {
12+
13+
public static void main(String[] args) {
14+
TreeNode tree = deserialize("[1,2,3,null,null,4,5]");
15+
System.out.println("args = " + serialize(tree));
16+
}
17+
18+
public static String rserialize(TreeNode root, String str) {
19+
if (root == null) {
20+
str += "null,";
21+
} else {
22+
str += str.valueOf(root.val) + ",";
23+
str = rserialize(root.left, str);
24+
str = rserialize(root.right, str);
25+
}
26+
return str;
27+
}
28+
29+
public static String serialize(TreeNode root) {
30+
String text = rserialize(root, "");
31+
while (text.endsWith("null,")) {
32+
int index = text.lastIndexOf("null,");
33+
text = text.substring(0, index);
34+
}
35+
if (text.endsWith(",")) {
36+
text = text.substring(0, text.length() - 1);
37+
}
38+
return text;
39+
}
40+
41+
public static TreeNode rdeserialize(List<String> list) {
42+
if (list == null || list.size() == 0) {
43+
return null;
44+
}
45+
if (list.get(0).equalsIgnoreCase("null")) {
46+
list.remove(0);
47+
return null;
48+
}
49+
50+
TreeNode root = new TreeNode(Integer.valueOf(list.get(0)));
51+
list.remove(0);
52+
root.left = rdeserialize(list);
53+
root.right = rdeserialize(list);
54+
55+
return root;
56+
}
57+
58+
public static TreeNode deserialize(String data) {
59+
data = data.substring(1, data.length() - 1);
60+
String[] nums = data.split(",");
61+
List<String> list = new LinkedList<String>(Arrays.asList(nums));
62+
return rdeserialize(list);
63+
}
64+
65+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/tree/btree/二叉树的最大深度.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -14,7 +14,7 @@
1414
public class 二叉树的最大深度 {
1515

1616
public static void main(String[] args) {
17-
TreeNode tree = TreeUtils.asTree(3, 9, 20, null, null, 15, 7);
17+
TreeNode tree = TreeUtils.deserialize("[3,9,20,null,null,15,7]");
1818
System.out.println("result = " + maxDepthInDFS(tree));
1919
Assertions.assertEquals(3, maxDepthInDFS(tree));
2020
Assertions.assertEquals(3, maxDepthInBFS(tree));

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/tree/btree/填充每个节点的下一个右侧节点指针.java‎

Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
package io.github.dunwu.algorithm.tree.btree;
2+
3+
import java.util.LinkedList;
4+
5+
/**
6+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
7+
* @since 2020-07-06
8+
*/
9+
public class 填充每个节点的下一个右侧节点指针 {
10+
11+
public Node connect(Node root) {
12+
if (root == null) return null;
13+
bfs(root);
14+
return root;
15+
}
16+
17+
/**
18+
* 基于 BFS 实现二叉树层次遍历。关键在于使用一个队列存储
19+
*/
20+
public void bfs(Node root) {
21+
LinkedList<Node> queue = new LinkedList<>();
22+
queue.offer(root);
23+
while (!queue.isEmpty()) {
24+
int size = queue.size();
25+
for (int i = 1; i < size; i++) {
26+
queue.get(i - 1).next = queue.get(i);
27+
}
28+
29+
for (int i = 0; i < size; i++) {
30+
Node node = queue.poll();
31+
if (node.left != null) queue.offer(node.left);
32+
if (node.right != null) queue.offer(node.right);
33+
}
34+
}
35+
}
36+
37+
private static class Node {
38+
39+
public int val;
40+
public Node left;
41+
public Node right;
42+
public Node next;
43+
44+
public Node(int val) { this.val = val; }
45+
46+
public Node(int val, Node left, Node right) {
47+
this.val = val;
48+
this.left = left;
49+
this.right = right;
50+
}
51+
52+
@Override
53+
public String toString() {
54+
return "Node{" +
55+
"val=" + val +
56+
'}';
57+
}
58+
59+
}
60+
61+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/tree/btree/填充每个节点的下一个右侧节点指针II.java‎

Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
package io.github.dunwu.algorithm.tree.btree;
2+
3+
import java.util.LinkedList;
4+
5+
/**
6+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
7+
* @since 2020-07-06
8+
*/
9+
public class 填充每个节点的下一个右侧节点指针II {
10+
11+
public Node connect(Node root) {
12+
if (root == null) return null;
13+
bfs(root);
14+
return root;
15+
}
16+
17+
/**
18+
* 基于 BFS 实现二叉树层次遍历。关键在于使用一个队列存储
19+
*/
20+
public void bfs(Node root) {
21+
LinkedList<Node> queue = new LinkedList<>();
22+
queue.offer(root);
23+
while (!queue.isEmpty()) {
24+
int size = queue.size();
25+
for (int i = 1; i < size; i++) {
26+
queue.get(i - 1).next = queue.get(i);
27+
}
28+
29+
for (int i = 0; i < size; i++) {
30+
Node node = queue.poll();
31+
if (node.left != null) queue.offer(node.left);
32+
if (node.right != null) queue.offer(node.right);
33+
}
34+
}
35+
}
36+
37+
private static class Node {
38+
39+
public int val;
40+
public Node left;
41+
public Node right;
42+
public Node next;
43+
44+
public Node(int val) { this.val = val; }
45+
46+
public Node(int val, Node left, Node right) {
47+
this.val = val;
48+
this.left = left;
49+
this.right = right;
50+
}
51+
52+
@Override
53+
public String toString() {
54+
return "Node{" +
55+
"val=" + val +
56+
'}';
57+
}
58+
59+
}
60+
61+
}

0 commit comments

Comments
 (0)