Skip to content

Commit 43e07b9

Browse files
xiaoningningxiaoningning
committed
print leaf path of general tree
1 parent d23298a commit 43e07b9

7 files changed

Lines changed: 125 additions & 33 deletions

File tree

‎IntArrayOps/src/IntArrayOps.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -166,7 +166,7 @@ else if (ai_1 < bj && bj < ai)
166166
if (ai < bj_1)
167167
return findK(a, i + 1, ra, b, lb, j - 1, k - 1 - (i - la));
168168
else // bj < ai_1
169-
return findK(a, la, i - 1, b, j + 1, rb, k - 1 - (j - lb) - 1);
169+
return findK(a, la, i - 1, b, j + 1, rb, k - 1 - (j - lb));
170170

171171
}
172172

‎PuzzleCoding/src/FindMiddleShiftedSorted.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,7 @@
33
public class FindMiddleShiftedSorted {
44
public static void main(String[] args){
55
int[] a1 = new int[]{15,17,1,3,6,7};
6-
int[] a2 = new int[]{15,16,17,18,1,7};
6+
int[] a2 = new int[]{15,16,17,18,1};
77
int[] a3 = new int[]{1,2,3,4};
88
findMiddleShiftedSorted(a1);
99
findMiddleShiftedSorted(a2);

‎PuzzleCoding/src/GenerateParentheses.java‎

Lines changed: 23 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -1,55 +1,55 @@
1-
21
public class GenerateParentheses {
3-
public static void main(String[] args){
2+
public static void main(String[] args) {
43
int N = 3;
5-
generateParentheses(new char[2*N], N, N, 0);
4+
generateParentheses(new char[2 * N], N, N, 0);
65

76
System.out.println(isGoodParentheses("(()][())".toCharArray()));
87
}
9-
public static void generateParentheses(char[] prefix, int left, int right, int level){
10-
if(left > right || left < 0)
8+
9+
public static void generateParentheses(char[] prefix, int left, int right, int level) {
10+
if (left > right)
1111
return;
12-
if(left ==0 && right == 0) {
12+
if (left == 0 && right == 0) {
1313
System.out.println(String.valueOf(prefix));
1414
return;
15-
}
16-
else {
17-
if(left>0){
15+
} else {
16+
if (left > 0 && right >= 0) {
1817
prefix[level] = '(';
19-
generateParentheses(prefix, left-1, right, level+1);
18+
generateParentheses(prefix, left - 1, right, level + 1);
2019
}
21-
if(right> 0){
20+
if (right > 0 && left >= 0) {
2221
prefix[level] = ')';
23-
generateParentheses(prefix, left, right-1, level+1);
22+
generateParentheses(prefix, left, right - 1, level + 1);
2423
}
2524
}
2625

2726
}
2827

29-
public static boolean isGoodParentheses(char[] s){
28+
29+
public static boolean isGoodParentheses(char[] s) {
3030

3131
int level1 = 0;
3232
int level2 = 0;
3333

34-
for(int i = 0 ; i < s.length; i++){
35-
if(level1==0)
36-
if(s[i] ==')')
34+
for (int i = 0; i < s.length; i++) {
35+
if (level1 == 0)
36+
if (s[i] == ')')
3737
return false;
38-
if(level2==0)
39-
if(s[i] ==']')
38+
if (level2 == 0)
39+
if (s[i] == ']')
4040
return false;
4141

42-
if(s[i] == '(')
42+
if (s[i] == '(')
4343
level1++;
44-
if(s[i]==')')
44+
if (s[i] == ')')
4545
level1--;
46-
if(s[i] == '[')
46+
if (s[i] == '[')
4747
level2++;
48-
if(s[i]==']')
48+
if (s[i] == ']')
4949
level2--;
5050

5151
}
5252

53-
return (level1==0)&&(level2==0);
53+
return (level1 == 0) && (level2 == 0);
5454
}
5555
}

‎PuzzleCoding/src/SpiralMatrix.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -16,7 +16,7 @@
1616
*/
1717
public class SpiralMatrix {
1818
public static void main(String[] args) {
19-
int N = 3;
19+
int N = 4;
2020
int[][] spiralMatrix = spiralMatrix(N);
2121
for (int i = 0; i < spiralMatrix.length; ++i)
2222
System.out.println(Arrays.toString(spiralMatrix[i]));

‎PuzzleCoding/src/StablePartition.java‎

Lines changed: 4 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -40,10 +40,11 @@ public static void stable2WayPartition(int[] a, int left, int right){
4040
i++;
4141
while (j<=right && a[j]<0)
4242
j++;
43+
44+
reverse(a, i, mid);
45+
reverse(a, mid+1,j-1);
4346
reverse(a, i, j-1);
44-
reverse(a, i, j-1-mid+i-1 );
45-
reverse(a, j-1-mid+i, j-1);
46-
// System.out.println(Arrays.toString(a));
47+
4748
}
4849

4950
public static void reverse(int[] a, int left, int right){

‎PuzzleCoding/src/StringAnagram.java‎

Lines changed: 2 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -50,12 +50,10 @@ public static boolean isPermutation(String s1, String s2) {
5050
char[] a2 = s2.toCharArray();
5151
for (char c : a2) {
5252
letter[c]--;
53-
if (letter[c] < 0)
54-
return false;
55-
5653
}
54+
5755
for(int i = 0; i < letter.length; ++i){
58-
if(letter[i]>0)
56+
if((letter[i]>0) ||(letter[i]<0))
5957
return false;
6058
}
6159
return true;

‎PuzzleCoding/src/TreeLeafPath.java‎

Lines changed: 93 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,93 @@
1+
import java.util.ArrayList;
2+
import java.util.Stack;
3+
import java.util.List;
4+
5+
/**
6+
* print out all leaf node path with non recursive method
7+
* The structure of node is *NOT* binary tree, is just a normal tree.
8+
* <p/>
9+
* <p/>
10+
* // print out all leaf node path
11+
* // 12
12+
* // 4 8 22
13+
* //1 2 3 9 18 24
14+
* <p/>
15+
* the output is like:
16+
* <p/>
17+
* 12, 4, 1,
18+
* 12, 4, 2,
19+
* 12, 4, 3,
20+
* 12, 4, 8, 9,
21+
* 12, 4, 8, 22, 18,
22+
* 12, 4, 8, 22, 24,
23+
*/
24+
25+
public class TreeLeafPath {
26+
public Integer value;
27+
public ArrayList<TreeLeafPath> children;
28+
29+
public TreeLeafPath(Integer v) {
30+
value = v;
31+
children = new ArrayList<TreeLeafPath>();
32+
}
33+
34+
public void addTree(TreeLeafPath node) {
35+
children.add(node);
36+
}
37+
38+
public static void printPath(Stack<TreeLeafPath> s) {
39+
List<TreeLeafPath> list = s.subList(0, s.size());
40+
for (int i = 0; i < list.size(); i++) {
41+
if(i+1 == list.size())
42+
System.out.print(list.get(i).value);
43+
else
44+
System.out.print(list.get(i).value+"->");
45+
}
46+
System.out.println();
47+
}
48+
49+
public static void leafPath(TreeLeafPath node, Stack<TreeLeafPath> stack) {
50+
51+
stack.push(node);
52+
53+
TreeLeafPath current = stack.peek();
54+
ArrayList<TreeLeafPath> children = current.children;
55+
56+
if (children.size() == 0) {
57+
printPath(stack);
58+
stack.pop();
59+
return;
60+
} else {
61+
for (TreeLeafPath c : children) {
62+
leafPath(c, stack);
63+
}
64+
stack.pop();
65+
return;
66+
}
67+
68+
}
69+
70+
public static void main(String[] args) {
71+
72+
TreeLeafPath root = new TreeLeafPath(12);
73+
TreeLeafPath node4 = new TreeLeafPath(4);
74+
TreeLeafPath node8 = new TreeLeafPath(8);
75+
TreeLeafPath node1 = new TreeLeafPath(1);
76+
TreeLeafPath node2 = new TreeLeafPath(2);
77+
TreeLeafPath node3 = new TreeLeafPath(3);
78+
TreeLeafPath node9 = new TreeLeafPath(9);
79+
TreeLeafPath node18 = new TreeLeafPath(18);
80+
TreeLeafPath node22 = new TreeLeafPath(22);
81+
node18.addTree(node22);
82+
node8.addTree(node9);
83+
node8.addTree(node18);
84+
node4.addTree(node1);
85+
node4.addTree(node2);
86+
node4.addTree(node3);
87+
root.addTree(node4);
88+
root.addTree(node8);
89+
90+
Stack<TreeLeafPath> stack = new Stack<TreeLeafPath>();
91+
leafPath(root, stack);
92+
}
93+
}

0 commit comments

Comments
 (0)