Skip to content

Commit 2032c7b

Browse files
dunwudunwu
committed
feat: 刷 leetcode
1 parent ecefd75 commit 2032c7b

11 files changed

+610
-73
lines changed

‎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 io.github.dunwu.algorithm.tree.TreeNode;
4+
import io.github.dunwu.algorithm.tree.TreeUtils;
5+
import org.junit.jupiter.api.Assertions;
6+
7+
import java.util.LinkedList;
8+
import java.util.List;
9+
10+
/**
11+
* <a href="https://leetcode.cn/problems/check-completeness-of-a-binary-tree/">958. 二叉树的完全性检验</a>
12+
*
13+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
14+
* @date 2025-08-18
15+
*/
16+
public class 二叉树的完全性检验 {
17+
18+
public static void main(String[] args) {
19+
Solution s = new Solution();
20+
Assertions.assertTrue(s.isCompleteTree(TreeUtils.buildTree(1, 2, 3, 4, 5, 6)));
21+
Assertions.assertFalse(s.isCompleteTree(TreeUtils.buildTree(1, 2, 3, 4, 5, null, 7)));
22+
}
23+
24+
static class Solution {
25+
26+
static class NodeInfo {
27+
28+
public int id;
29+
public TreeNode node;
30+
31+
public NodeInfo(int id, TreeNode node) {
32+
this.id = id;
33+
this.node = node;
34+
}
35+
36+
}
37+
38+
public boolean isCompleteTree(TreeNode root) {
39+
40+
if (root == null) { return false; }
41+
42+
int id = 1;
43+
LinkedList<NodeInfo> q = new LinkedList<>();
44+
q.offer(new NodeInfo(id, root));
45+
46+
while (!q.isEmpty()) {
47+
int size = q.size();
48+
for (int i = 0; i < size; i++) {
49+
NodeInfo info = q.poll();
50+
if (info.id != id) { return false; }
51+
if (info.node.left != null) { q.offer(new NodeInfo(id * 2, info.node.left)); }
52+
if (info.node.right != null) { q.offer(new NodeInfo(id * 2 + 1, info.node.right)); }
53+
id++;
54+
}
55+
}
56+
return true;
57+
}
58+
59+
}
60+
61+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/tree/btree/二叉树的层平均值.java‎

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
package io.github.dunwu.algorithm.tree.btree;
2+
3+
import io.github.dunwu.algorithm.tree.TreeNode;
4+
import io.github.dunwu.algorithm.tree.TreeUtils;
5+
import org.junit.jupiter.api.Assertions;
6+
7+
import java.util.LinkedList;
8+
import java.util.List;
9+
10+
/**
11+
* <a href="https://leetcode.cn/problems/average-of-levels-in-binary-tree/">637. 二叉树的层平均值</a>
12+
*
13+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
14+
* @date 2025-08-18
15+
*/
16+
public class 二叉树的层平均值 {
17+
18+
public static void main(String[] args) {
19+
Solution s = new Solution();
20+
Assertions.assertArrayEquals(new Double[] { 3.00000, 14.50000, 11.00000 },
21+
s.averageOfLevels(TreeUtils.buildTree(3, 9, 20, null, null, 15, 7)).toArray());
22+
Assertions.assertArrayEquals(new Double[] { 3.00000, 14.50000, 11.00000 },
23+
s.averageOfLevels(TreeUtils.buildTree(3, 9, 20, 15, 7)).toArray());
24+
}
25+
26+
static class Solution {
27+
28+
public List<Double> averageOfLevels(TreeNode root) {
29+
if (root == null) { return new LinkedList<>(); }
30+
31+
List<Double> res = new LinkedList<>();
32+
LinkedList<TreeNode> q = new LinkedList<>();
33+
q.offer(root);
34+
35+
while (!q.isEmpty()) {
36+
double sum = 0;
37+
int size = q.size();
38+
for (int i = 0; i < size; i++) {
39+
TreeNode node = q.poll();
40+
sum += node.val;
41+
if (node.left != null) { q.offer(node.left); }
42+
if (node.right != null) { q.offer(node.right); }
43+
}
44+
res.add(sum / size);
45+
}
46+
return res;
47+
}
48+
49+
}
50+
51+
}

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

Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
package io.github.dunwu.algorithm.tree.btree;
2+
3+
import io.github.dunwu.algorithm.tree.TreeNode;
4+
import io.github.dunwu.algorithm.tree.TreeUtils;
5+
import org.junit.jupiter.api.Assertions;
6+
7+
import java.util.LinkedList;
8+
9+
/**
10+
* <a href="https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/">104. 二叉树的最大深度</a>
11+
*
12+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
13+
* @date 2025-08-18
14+
*/
15+
public class 二叉树的最大宽度 {
16+
17+
public static void main(String[] args) {
18+
Solution s = new Solution();
19+
Assertions.assertEquals(4, s.widthOfBinaryTree(TreeUtils.buildTree(1, 3, 2, 5, 3, null, 9)));
20+
Assertions.assertEquals(7, s.widthOfBinaryTree(TreeUtils.buildTree(1, 3, 2, 5, null, null, 9, 6, null, 7)));
21+
}
22+
23+
static class Solution {
24+
25+
public static class NodeInfo {
26+
27+
public int id;
28+
public TreeNode node;
29+
30+
public NodeInfo(int id, TreeNode node) {
31+
this.id = id;
32+
this.node = node;
33+
}
34+
35+
}
36+
37+
public int widthOfBinaryTree(TreeNode root) {
38+
39+
int maxWidth = 0;
40+
LinkedList<NodeInfo> q = new LinkedList<>();
41+
q.offer(new NodeInfo(1, root));
42+
43+
while (!q.isEmpty()) {
44+
int size = q.size();
45+
int begin = 0, end = 0;
46+
for (int i = 0; i < size; i++) {
47+
NodeInfo cur = q.poll();
48+
if (i == 0) {
49+
begin = cur.id;
50+
}
51+
if (i == size - 1) {
52+
end = cur.id;
53+
}
54+
if (cur.node.left != null) {
55+
q.offer(new NodeInfo(cur.id * 2, cur.node.left));
56+
}
57+
if (cur.node.right != null) {
58+
q.offer(new NodeInfo(cur.id * 2 + 1, cur.node.right));
59+
}
60+
}
61+
int width = end - begin + 1;
62+
maxWidth = Math.max(maxWidth, width);
63+
}
64+
return maxWidth;
65+
}
66+
67+
}
68+
69+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/tree/btree/二叉树的锯齿形层次遍历.java‎

Lines changed: 49 additions & 52 deletions
Original file line numberDiff line numberDiff line change
@@ -11,68 +11,65 @@
1111
import java.util.List;
1212

1313
/**
14-
* <code>103. 二叉树的锯齿形层次遍历</code> 算法实现
15-
* <p>
16-
* 给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
17-
* <p>
18-
* 例如：给定二叉树 [3,9,20,null,null,15,7],
19-
* <pre>
20-
* 3
21-
* / \
22-
* 9 20
23-
* / \
24-
* 15 7
25-
* </pre>
26-
* 返回锯齿形层次遍历如下：
27-
* <pre>
28-
* [
29-
* [3],
30-
* [20,9],
31-
* [15,7]
32-
* ]
33-
* </pre>
14+
* <a href="https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/">103. 二叉树的锯齿形层次遍历</a>
3415
*
35-
* @see <a href="https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/">103. 二叉树的锯齿形层次遍历</a>
16+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
17+
* @date 2025-08-18
3618
*/
3719
public class 二叉树的锯齿形层次遍历 {
3820

3921
public static void main(String[] args) {
40-
TreeNode tree = TreeUtils.buildTree(3, 9, 20, null, null, 15, 7);
41-
List<List<Integer>> resultList = zigzagLevelOrder(tree);
42-
System.out.println(resultList);
43-
List<List<Integer>> expectList = new LinkedList<>();
44-
expectList.add(Arrays.asList(3));
45-
expectList.add(Arrays.asList(20, 9));
46-
expectList.add(Arrays.asList(15, 7));
47-
Assertions.assertArrayEquals(expectList.toArray(), resultList.toArray());
22+
23+
Solution s = new Solution();
24+
25+
TreeNode root = TreeUtils.buildTree(3, 9, 20, null, null, 15, 7);
26+
List<List<Integer>> expect = new LinkedList<>();
27+
expect.add(Arrays.asList(3));
28+
expect.add(Arrays.asList(20, 9));
29+
expect.add(Arrays.asList(15, 7));
30+
Assertions.assertArrayEquals(expect.toArray(), s.zigzagLevelOrder(root).toArray());
31+
32+
TreeNode root2 = TreeUtils.buildTree(1);
33+
List<List<Integer>> expect2 = new LinkedList<>();
34+
expect2.add(Arrays.asList(1));
35+
Assertions.assertArrayEquals(expect2.toArray(), s.zigzagLevelOrder(root2).toArray());
36+
37+
TreeNode root3 = TreeUtils.buildTree();
38+
List<List<Integer>> expect3 = new LinkedList<>();
39+
Assertions.assertArrayEquals(expect3.toArray(), s.zigzagLevelOrder(root3).toArray());
4840
}
4941

50-
public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
51-
List<List<Integer>> result = new LinkedList<>();
52-
LinkedList<TreeNode> queue = new LinkedList<>();
53-
if (root == null) return result;
54-
queue.offer(root);
55-
boolean reverse = false;
56-
while (!queue.isEmpty()) {
57-
int size = queue.size();
58-
List<Integer> list = new ArrayList<>();
59-
for (int i = 0; i < size; i++) {
60-
TreeNode node = queue.poll();
61-
if (node != null) {
62-
list.add(node.val);
63-
if (node.left != null) queue.offer(node.left);
64-
if (node.right != null) queue.offer(node.right);
42+
static class Solution {
43+
44+
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
45+
46+
if (root == null) { return new LinkedList<>(); }
47+
48+
LinkedList<TreeNode> q = new LinkedList<>();
49+
LinkedList<List<Integer>> res = new LinkedList<>();
50+
q.offer(root);
51+
52+
boolean reverse = false;
53+
while (!q.isEmpty()) {
54+
int size = q.size();
55+
List<Integer> cur = new LinkedList<>();
56+
57+
for (int i = 0; i < size; i++) {
58+
TreeNode node = q.poll();
59+
cur.add(node.val);
60+
if (node.left != null) { q.offer(node.left); }
61+
if (node.right != null) { q.offer(node.right); }
6562
}
63+
if (reverse) {
64+
Collections.reverse(cur);
65+
}
66+
res.add(cur);
67+
reverse = !reverse;
6668
}
67-
if (reverse) {
68-
Collections.reverse(list);
69-
result.add(list);
70-
} else {
71-
result.add(list);
72-
}
73-
reverse = !reverse;
69+
70+
return res;
7471
}
75-
return result;
72+
7673
}
7774

7875
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/tree/btree/删点成林.java‎

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
package io.github.dunwu.algorithm.tree.btree;
2+
3+
import io.github.dunwu.algorithm.tree.TreeNode;
4+
import io.github.dunwu.algorithm.tree.TreeUtils;
5+
import org.junit.jupiter.api.Assertions;
6+
7+
import java.util.LinkedList;
8+
import java.util.List;
9+
10+
/**
11+
* <a href="https://leetcode.cn/problems/delete-nodes-and-return-forest/">1110. 删点成林</a>
12+
*
13+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
14+
* @date 2025-08-18
15+
*/
16+
public class 删点成林 {
17+
18+
public static void main(String[] args) {
19+
Solution s = new Solution();
20+
21+
TreeNode input = TreeUtils.buildTree(1, 2, 3, 4, 5, 6, 7);
22+
List<TreeNode> output = s.delNodes(input, new int[] { 3, 5 });
23+
// List<Integer> result1 = TreeUtils.toValueList(output);
24+
// Assertions.assertArrayEquals(new Integer[] { 5, 4, null, 1, 3, null, null, 2 }, result1.toArray());
25+
26+
}
27+
28+
static class Solution {
29+
30+
List<TreeNode> res = new LinkedList<>();
31+
32+
public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
33+
if (root == null) return new LinkedList<>();
34+
35+
if (isDel(root.val, to_delete)) {
36+
if (root.left == null && root.right == null) {
37+
root = null;
38+
return new LinkedList<>();
39+
} else {
40+
41+
}
42+
} else {
43+
res.addAll(delNodes(root.left, to_delete));
44+
res.addAll(delNodes(root.right, to_delete));
45+
}
46+
return res;
47+
}
48+
49+
public boolean isDel(int val, int[] to_delete) {
50+
for (int num : to_delete) {
51+
if (val == num) return true;
52+
}
53+
return false;
54+
}
55+
56+
}
57+
58+
}

0 commit comments

Comments
 (0)