Skip to content

Commit afaa9e9

Browse files
algorithmzuoalgorithmzuo
committed
add class 07
1 parent 8d26585 commit afaa9e9

5 files changed

Lines changed: 218 additions & 0 deletions

File tree

‎src/class07/Code01_BinaryTreeLevelOrderTraversalII.java‎

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
package class07;
2+
3+
import java.util.LinkedList;
4+
import java.util.List;
5+
import java.util.Queue;
6+
7+
// 测试链接：https://leetcode.com/problems/binary-tree-level-order-traversal-ii
8+
public class Code01_BinaryTreeLevelOrderTraversalII {
9+
10+
public static class TreeNode {
11+
public int val;
12+
public TreeNode left;
13+
public TreeNode right;
14+
15+
TreeNode(int val) {
16+
this.val = val;
17+
}
18+
}
19+
20+
public List<List<Integer>> levelOrderBottom(TreeNode root) {
21+
List<List<Integer>> ans = new LinkedList<>();
22+
if (root == null) {
23+
return ans;
24+
}
25+
Queue<TreeNode> queue = new LinkedList<>();
26+
queue.add(root);
27+
while (!queue.isEmpty()) {
28+
int size = queue.size();
29+
List<Integer> curAns = new LinkedList<>();
30+
for (int i = 0; i < size; i++) {
31+
TreeNode curNode = queue.poll();
32+
curAns.add(curNode.val);
33+
if (curNode.left != null) {
34+
queue.add(curNode.left);
35+
}
36+
if (curNode.right != null) {
37+
queue.add(curNode.right);
38+
}
39+
}
40+
ans.add(0, curAns);
41+
}
42+
return ans;
43+
}
44+
45+
}

‎src/class07/Code02_BalancedBinaryTree.java‎

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
package class07;
2+
3+
// 测试链接：https://leetcode.com/problems/balanced-binary-tree
4+
public class Code02_BalancedBinaryTree {
5+
6+
public static class TreeNode {
7+
public int val;
8+
public TreeNode left;
9+
public TreeNode right;
10+
11+
TreeNode(int val) {
12+
this.val = val;
13+
}
14+
}
15+
16+
public static class Info {
17+
public boolean isBalanced;
18+
public int height;
19+
20+
public Info(boolean i, int h) {
21+
isBalanced = i;
22+
height = h;
23+
}
24+
}
25+
26+
public static boolean isBalanced(TreeNode root) {
27+
return process(root).isBalanced;
28+
}
29+
30+
public static Info process(TreeNode root) {
31+
if (root == null) {
32+
return new Info(true, 0);
33+
}
34+
Info leftInfo = process(root.left);
35+
Info rightInfo = process(root.right);
36+
int height = Math.max(leftInfo.height, rightInfo.height) + 1;
37+
boolean isBalanced = leftInfo.isBalanced && rightInfo.isBalanced
38+
&& Math.abs(leftInfo.height - rightInfo.height) < 2;
39+
return new Info(isBalanced, height);
40+
}
41+
42+
}

‎src/class07/Code03_PathSum.java‎

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package class07;
2+
3+
public class Code03_PathSum {
4+
5+
// 测试链接：https://leetcode.com/problems/path-sum
6+
public static class TreeNode {
7+
public int val;
8+
public TreeNode left;
9+
public TreeNode right;
10+
11+
TreeNode(int val) {
12+
this.val = val;
13+
}
14+
}
15+
16+
public static boolean hasPathSum(TreeNode root, int sum) {
17+
if (root == null) {
18+
return false;
19+
}
20+
return process(root, sum);
21+
}
22+
23+
public static boolean process(TreeNode root, int rest) {
24+
if (root.left == null && root.right == null) {
25+
return root.val == rest;
26+
}
27+
boolean ans = root.left != null ? process(root.left, rest - root.val) : false;
28+
ans |= root.right != null ? process(root.right, rest - root.val) : false;
29+
return ans;
30+
}
31+
32+
}

‎src/class07/Code04_PathSumII.java‎

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
package class07;
2+
3+
import java.util.ArrayList;
4+
import java.util.LinkedList;
5+
import java.util.List;
6+
7+
public class Code04_PathSumII {
8+
9+
// 测试链接：https://leetcode.com/problems/path-sum-ii
10+
public static class TreeNode {
11+
public int val;
12+
public TreeNode left;
13+
public TreeNode right;
14+
15+
TreeNode(int val) {
16+
this.val = val;
17+
}
18+
}
19+
20+
public static List<List<Integer>> pathSum(TreeNode root, int sum) {
21+
List<List<Integer>> ans = new ArrayList<>();
22+
if (root == null) {
23+
return ans;
24+
}
25+
LinkedList<Integer> path = new LinkedList<>();
26+
process(root, sum, path, ans);
27+
return ans;
28+
}
29+
30+
public static void process(TreeNode root, int rest, LinkedList<Integer> path, List<List<Integer>> ans) {
31+
path.addLast(root.val);
32+
if (root.left == null && root.right == null) {
33+
if (root.val == rest) {
34+
ans.add(copy(path));
35+
}
36+
} else {
37+
if (root.left != null) {
38+
process(root.left, rest - root.val, path, ans);
39+
}
40+
if (root.right != null) {
41+
process(root.right, rest - root.val, path, ans);
42+
}
43+
}
44+
path.pollLast();
45+
}
46+
47+
public static List<Integer> copy(LinkedList<Integer> path) {
48+
List<Integer> ans = new ArrayList<>();
49+
for (Integer num : path) {
50+
ans.add(num);
51+
}
52+
return ans;
53+
}
54+
55+
}

‎src/class07/Code05_GetMax.java‎

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
package class07;
2+
3+
public class Code05_GetMax {
4+
5+
public static int flip(int n) {
6+
return n ^ 1;
7+
}
8+
9+
public static int sign(int n) {
10+
11+
return flip((n >> 31) & 1);
12+
}
13+
14+
public static int getMax1(int a, int b) {
15+
int c = a - b;
16+
int scA = sign(c);
17+
int scB = flip(scA);
18+
return a * scA + b * scB;
19+
}
20+
21+
public static int getMax2(int a, int b) {
22+
int c = a - b;
23+
int sa = sign(a);
24+
int sb = sign(b);
25+
int sc = sign(c);
26+
int difSab = sa ^ sb;
27+
int sameSab = flip(difSab);
28+
int returnA = difSab * sa + sameSab * sc;
29+
int returnB = flip(returnA);
30+
return a * returnA + b * returnB;
31+
}
32+
33+
public static void main(String[] args) {
34+
int a = -16;
35+
int b = -19;
36+
System.out.println(getMax1(a, b));
37+
System.out.println(getMax2(a, b));
38+
a = 2147483647;
39+
b = -2147480000;
40+
System.out.println(getMax1(a, b)); // wrong answer because of overflow
41+
System.out.println(getMax2(a, b));
42+
}
43+
44+
}

0 commit comments

Comments
 (0)