Skip to content

Commit d051cef

Browse files
algorithmzuoalgorithmzuo
committed
modify code
1 parent afaa9e9 commit d051cef

5 files changed

Lines changed: 215 additions & 30 deletions

File tree

‎src/class06/Code07_BalancedBinaryTree.java‎

Lines changed: 11 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -13,6 +13,12 @@ public static class TreeNode {
1313
}
1414
}
1515

16+
17+
18+
public static boolean isBalanced(TreeNode root) {
19+
return process(root).isBalanced;
20+
}
21+
1622
public static class Info {
1723
public boolean isBalanced;
1824
public int height;
@@ -23,16 +29,13 @@ public Info(boolean i, int h) {
2329
}
2430
}
2531

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+
public static Info process(TreeNode x) {
33+
if (x == null) {
3234
return new Info(true, 0);
3335
}
34-
Info leftInfo = process(root.left);
35-
Info rightInfo = process(root.right);
36+
// x != null
37+
Info leftInfo = process(x.left);
38+
Info rightInfo = process(x.right);
3639
int height = Math.max(leftInfo.height, rightInfo.height) + 1;
3740
boolean isBalanced = leftInfo.isBalanced && rightInfo.isBalanced
3841
&& Math.abs(leftInfo.height - rightInfo.height) < 2;

‎src/class07/Code01_BinaryTreeLevelOrderTraversalII.java‎

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,10 @@
11
package class07;
22

3+
import java.util.ArrayList;
34
import java.util.LinkedList;
45
import java.util.List;
56
import java.util.Queue;
7+
import java.util.Stack;
68

79
// 测试链接：https://leetcode.com/problems/binary-tree-level-order-traversal-ii
810
public class Code01_BinaryTreeLevelOrderTraversalII {
@@ -42,4 +44,67 @@ public List<List<Integer>> levelOrderBottom(TreeNode root) {
4244
return ans;
4345
}
4446

47+
public static void main(String[] args) {
48+
int testTime = 1000;
49+
long start;
50+
long end;
51+
52+
System.out.println("hello!");
53+
// ArrayList<Integer> arr1 = new ArrayList<>();
54+
// start = System.currentTimeMillis();
55+
// for (int i = 0; i < testTime; i++) {
56+
// arr1.add(0, i);
57+
// }
58+
// end = System.currentTimeMillis();
59+
// System.out.println(end - start);
60+
//
61+
// LinkedList<Integer> arr2 = new LinkedList<>();
62+
// start = System.currentTimeMillis();
63+
// for (int i = 0; i < testTime; i++) {
64+
// arr2.add(0, i);
65+
// }
66+
// end = System.currentTimeMillis();
67+
// System.out.println(end - start);
68+
// System.out.println("=====");
69+
70+
testTime = 10000000;
71+
Stack<Integer> stack1 = new Stack<>();
72+
start = System.currentTimeMillis();
73+
for (int i = 0; i < testTime; i++) {
74+
stack1.add(i);
75+
}
76+
while (!stack1.isEmpty()) {
77+
stack1.pop();
78+
}
79+
end = System.currentTimeMillis();
80+
System.out.println(end - start);
81+
82+
int[] stack2 = new int[testTime];
83+
int index = 0;
84+
start = System.currentTimeMillis();
85+
for (int i = 0; i < testTime; i++) {
86+
stack2[index++] = i;
87+
}
88+
while (index != 0) {
89+
int a = stack2[--index];
90+
}
91+
end = System.currentTimeMillis();
92+
System.out.println(end - start);
93+
94+
// while (!s.isEmpty()) {
95+
// System.out.println(s.pollLast());
96+
// }
97+
//
98+
// int[] sta = new int[100];
99+
// int index = 0;
100+
// sta[index++] = 1;
101+
// sta[index++] = 2;
102+
// sta[index++] = 3;
103+
//
104+
// System.out.println(sta[--index]);
105+
// System.out.println(sta[--index]);
106+
// System.out.println(sta[--index]);
107+
108+
}
109+
45110
}

‎src/class07/Code03_PathSum.java‎

Lines changed: 35 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -13,20 +13,48 @@ public static class TreeNode {
1313
}
1414
}
1515

16+
public static boolean isSum = false;
17+
1618
public static boolean hasPathSum(TreeNode root, int sum) {
1719
if (root == null) {
1820
return false;
1921
}
20-
return process(root, sum);
22+
isSum = false;
23+
process(root, 0, sum);
24+
return isSum;
2125
}
2226

23-
public static boolean process(TreeNode root, int rest) {
24-
if (root.left == null && root.right == null) {
25-
return root.val == rest;
27+
public static void process(TreeNode x, int preSum, int sum) {
28+
if (x.left == null && x.right == null) {
29+
if (x.val + preSum == sum) {
30+
isSum = true;
31+
}
32+
return;
33+
}
34+
// x是非叶节点
35+
preSum += x.val;
36+
if (x.left != null) {
37+
process(x.left, preSum, sum);
38+
}
39+
if (x.right != null) {
40+
process(x.right, preSum, sum);
2641
}
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;
3042
}
3143

44+
// public static boolean hasPathSum(TreeNode root, int sum) {
45+
// if (root == null) {
46+
// return false;
47+
// }
48+
// return process(root, sum);
49+
// }
50+
//
51+
// public static boolean process(TreeNode root, int rest) {
52+
// if (root.left == null && root.right == null) {
53+
// return root.val == rest;
54+
// }
55+
// boolean ans = root.left != null ? process(root.left, rest - root.val) : false;
56+
// ans |= root.right != null ? process(root.right, rest - root.val) : false;
57+
// return ans;
58+
// }
59+
3260
}

‎src/class07/Code04_PathSumII.java‎

Lines changed: 19 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -22,29 +22,33 @@ public static List<List<Integer>> pathSum(TreeNode root, int sum) {
2222
if (root == null) {
2323
return ans;
2424
}
25-
LinkedList<Integer> path = new LinkedList<>();
26-
process(root, sum, path, ans);
25+
ArrayList<Integer> path = new ArrayList<>();
26+
process(root, path, 0, sum, ans);
2727
return ans;
2828
}
2929

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) {
30+
public static void process(TreeNode x, List<Integer> path, int preSum, int sum, List<List<Integer>> ans) {
31+
if (x.left == null && x.right == null) {
32+
if (preSum + x.val == sum) {
33+
path.add(x.val);
3434
ans.add(copy(path));
35+
path.remove(path.size() - 1);
3536
}
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-
}
37+
return;
38+
}
39+
// x 非叶节点
40+
path.add(x.val);
41+
preSum += x.val;
42+
if (x.left != null) {
43+
process(x.left, path, preSum, sum, ans);
44+
}
45+
if (x.right != null) {
46+
process(x.right, path, preSum, sum, ans);
4347
}
44-
path.pollLast();
48+
path.remove(path.size() - 1);
4549
}
4650

47-
public static List<Integer> copy(LinkedList<Integer> path) {
51+
public static List<Integer> copy(List<Integer> path) {
4852
List<Integer> ans = new ArrayList<>();
4953
for (Integer num : path) {
5054
ans.add(num);

‎src/class07/Code06_IsBinarySearchTree.java‎

Lines changed: 85 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,85 @@
1+
package class07;
2+
3+
public class Code06_IsBinarySearchTree {
4+
5+
public static class TreeNode {
6+
public int val;
7+
public TreeNode left;
8+
public TreeNode right;
9+
10+
TreeNode(int val) {
11+
this.val = val;
12+
}
13+
}
14+
15+
public static class Info {
16+
public boolean isBST;
17+
public int max;
18+
public int min;
19+
20+
public Info(boolean is, int ma, int mi) {
21+
isBST = is;
22+
max = ma;
23+
min = mi;
24+
}
25+
}
26+
27+
// public static Info process(TreeNode x) {
28+
// if (x == null) {
29+
// return null;
30+
// }
31+
// Info leftInfo = process(x.left);
32+
// Info rightInfo = process(x.right);
33+
// int max = x.val;
34+
// int min = x.val;
35+
// if (leftInfo != null) {
36+
// max = Math.max(leftInfo.max, max);
37+
// min = Math.min(leftInfo.min, min);
38+
// }
39+
// if (rightInfo != null) {
40+
// max = Math.max(rightInfo.max, max);
41+
// min = Math.min(rightInfo.min, min);
42+
// }
43+
// boolean isBST = true;
44+
// if (leftInfo != null && !leftInfo.isBST) {
45+
// isBST = false;
46+
// }
47+
// if (rightInfo != null && !rightInfo.isBST) {
48+
// isBST = false;
49+
// }
50+
// boolean leftMaxLessX = leftInfo == null ? true : (leftInfo.max < x.val);
51+
// boolean rightMinMoreX = rightInfo == null ? true : (rightInfo.min > x.val);
52+
// if (!(leftMaxLessX && rightMinMoreX)) {
53+
// isBST = false;
54+
// }
55+
// return new Info(isBST, max, min);
56+
// }
57+
58+
public static Info process(TreeNode x) {
59+
if (x == null) {
60+
return null;
61+
}
62+
Info leftInfo = process(x.left);
63+
Info rightInfo = process(x.right);
64+
int max = x.val;
65+
int min = x.val;
66+
if (leftInfo != null) {
67+
max = Math.max(leftInfo.max, max);
68+
min = Math.min(leftInfo.min, min);
69+
}
70+
if (rightInfo != null) {
71+
max = Math.max(rightInfo.max, max);
72+
min = Math.min(rightInfo.min, min);
73+
}
74+
boolean isBST = false;
75+
boolean leftIsBst = leftInfo == null ? true : leftInfo.isBST;
76+
boolean rightIsBst = rightInfo == null ? true : rightInfo.isBST;
77+
boolean leftMaxLessX = leftInfo == null ? true : (leftInfo.max < x.val);
78+
boolean rightMinMoreX = rightInfo == null ? true : (rightInfo.min > x.val);
79+
if (leftIsBst && rightIsBst && leftMaxLessX && rightMinMoreX) {
80+
isBST = true;
81+
}
82+
return new Info(isBST, max, min);
83+
}
84+
85+
}

0 commit comments

Comments
 (0)