Skip to content

Commit d53ea1c

Browse files
gzc426gzc426
authored
Merge pull request gzc426#395 from za1275952454/master
1
2 parents 15c58a3 + f53624e commit d53ea1c

File tree

4 files changed

+232
-31
lines changed

4 files changed

+232
-31
lines changed

‎2018.12.08-leetcode105/fish.md

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
```
2+
public class Solution {
3+
public static TreeNode binaryTree(TreeNode node, List<Integer> preOrder, List<Integer> inOrder) {
4+
if (!preOrder.isEmpty()) {
5+
Integer val = preOrder.get(0);
6+
int preIndex = preOrder.indexOf(val);
7+
int inIndex = inOrder.indexOf(val);
8+
List<Integer> plOrder = preOrder.subList(preIndex + 1, inIndex + 1);
9+
List<Integer> prOrder = preOrder.subList(inIndex + 1, preOrder.size());
10+
11+
List<Integer> ilOrder = inOrder.subList(0, inIndex);
12+
List<Integer> irOrder = inOrder.subList(inIndex + 1, inOrder.size());
13+
if (node == null) {
14+
node = new TreeNode(val, null, null);
15+
}
16+
TreeNode lnode = null,rnode = null;
17+
if (!plOrder.isEmpty()){
18+
lnode = new TreeNode(plOrder.get(0), null, null);
19+
}
20+
if (!prOrder.isEmpty()) {
21+
rnode = new TreeNode(prOrder.get(0), null, null);
22+
}
23+
node.setLeft(lnode);
24+
node.setRight(rnode);
25+
binaryTree(lnode, plOrder, ilOrder);
26+
binaryTree(rnode, prOrder, irOrder);
27+
}
28+
return node;
29+
}
30+
31+
public static void main(String[] args) {
32+
List<Integer> preOrder = new ArrayList<>();
33+
preOrder.add(1);
34+
preOrder.add(4);
35+
preOrder.add(6);
36+
preOrder.add(8);
37+
preOrder.add(9);
38+
preOrder.add(10);
39+
preOrder.add(11);
40+
List<Integer> inOrder = new ArrayList<>();
41+
inOrder.add(6);
42+
inOrder.add(4);
43+
inOrder.add(1);
44+
inOrder.add(9);
45+
inOrder.add(8);
46+
inOrder.add(10);
47+
inOrder.add(11);
48+
System.out.println(binaryTree(null, preOrder, inOrder));
49+
}
50+
}
51+
52+
@Data
53+
@AllArgsConstructor
54+
@NoArgsConstructor
55+
@ToString
56+
class TreeNode {
57+
private int val;
58+
private TreeNode left;
59+
private TreeNode right;
60+
}

‎2018.12.09-leetcode106/fish.md

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
```
2+
public class Solution {
3+
public static TreeNode binaryTree(TreeNode node, List<Integer> aftOrder, List<Integer> inOrder) {
4+
if (!aftOrder.isEmpty()){
5+
int size = aftOrder.size();
6+
Integer val = aftOrder.get(aftOrder.size() - 1);
7+
int index = inOrder.indexOf(val);
8+
9+
List<Integer> leftAftOrder = aftOrder.subList(0, index);
10+
List<Integer> rightAftOrder = aftOrder.subList(index, size - 1);
11+
12+
List<Integer> leftInOrder = inOrder.subList(0, index);
13+
List<Integer> rightInOrder = inOrder.subList(index + 1, size);
14+
15+
if (node == null) {
16+
node = new TreeNode(val, null, null);
17+
}
18+
19+
TreeNode leftNode = null, rightNode = null;
20+
if (!leftAftOrder.isEmpty()){
21+
leftNode = new TreeNode(leftAftOrder.get(leftAftOrder.size() - 1), null, null);
22+
node.setLeft(leftNode);
23+
}
24+
if (!rightAftOrder.isEmpty()){
25+
rightNode = new TreeNode(rightAftOrder.get(rightAftOrder.size() - 1), null, null);
26+
node.setRight(rightNode);
27+
}
28+
29+
binaryTree(leftNode, leftAftOrder, leftInOrder);
30+
binaryTree(rightNode, rightAftOrder, rightInOrder);
31+
}
32+
return node;
33+
}
34+
35+
public static void main(String[] args) {
36+
List<Integer> aftOrder = new ArrayList<>();
37+
aftOrder.add(22);
38+
aftOrder.add(16);
39+
aftOrder.add(9);
40+
aftOrder.add(15);
41+
aftOrder.add(7);
42+
aftOrder.add(20);
43+
aftOrder.add(3);
44+
List<Integer> inOrder = new ArrayList<>();
45+
inOrder.add(22);
46+
inOrder.add(9);
47+
inOrder.add(16);
48+
inOrder.add(3);
49+
inOrder.add(15);
50+
inOrder.add(20);
51+
inOrder.add(7);
52+
System.out.println(binaryTree(null, aftOrder, inOrder));
53+
}
54+
}
55+
56+
@Data
57+
@AllArgsConstructor
58+
@NoArgsConstructor
59+
@ToString
60+
class TreeNode {
61+
private int val;
62+
private TreeNode left;
63+
private TreeNode right;
64+
}

‎2018.12.10-leetcode107/fish.md

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
```
2+
public class Solution {
3+
private static LinkedList<List<Integer>> result = new LinkedList<>();
4+
5+
public static void traversalBinaryTree(TreeNode node) {
6+
if (node != null) {
7+
List<Integer> list = new ArrayList<>(node.getVal());
8+
list.add(node.getVal());
9+
result.addFirst(list);
10+
11+
TreeNode left = node.getLeft();
12+
TreeNode right = node.getRight();
13+
traversalBinaryTree(left, 1);
14+
traversalBinaryTree(right, 1);
15+
}
16+
}
17+
18+
public static void traversalBinaryTree(TreeNode node, int level) {
19+
if (node != null) {
20+
List<Integer> list;
21+
if (result.size() == level) {
22+
list = new ArrayList<>();
23+
result.addFirst(list);
24+
}else {
25+
list = result.get(result.size() - 1- level);
26+
}
27+
list.add(node.getVal());
28+
29+
TreeNode left = node.getLeft();
30+
TreeNode right = node.getRight();
31+
32+
traversalBinaryTree(left, level + 1);
33+
traversalBinaryTree(right, level + 1);
34+
}
35+
}
36+
37+
public static void main(String[] args) {
38+
TreeNode r3r = new TreeNode(7, null, null);
39+
TreeNode r3l = new TreeNode(15, null, null);
40+
41+
// TreeNode l3r = new TreeNode(18, null, null);
42+
// TreeNode l3l = new TreeNode(22, null, null);
43+
44+
TreeNode l2r = new TreeNode(20, r3l, r3r);
45+
TreeNode l2l = new TreeNode(9, null, null);
46+
TreeNode root = new TreeNode(3, l2l, l2r);
47+
traversalBinaryTree(root);
48+
System.out.println(result);
49+
}
50+
}
51+
52+
@Data
53+
@AllArgsConstructor
54+
@NoArgsConstructor
55+
@ToString
56+
class TreeNode {
57+
private int val;
58+
private TreeNode left;
59+
private TreeNode right;

‎fish.md

Lines changed: 49 additions & 31 deletions
Original file line numberDiff line numberDiff line change
@@ -1,42 +1,60 @@
1-
```````
1+
```
22
public class Solution {
3-
public static List<List<Integer>> levelOrder(TreeNode root) {
4-
List<List<Integer>> list = new ArrayList<>();
5-
if (root == null) {
6-
return list;
7-
}
8-
levelOrder(list, root, 0);
9-
return list;
10-
}
3+
public static TreeNode binaryTree(TreeNode node, List<Integer> preOrder, List<Integer> inOrder) {
4+
if (!preOrder.isEmpty()) {
5+
Integer val = preOrder.get(0);
6+
int preIndex = preOrder.indexOf(val);
7+
int inIndex = inOrder.indexOf(val);
8+
List<Integer> plOrder = preOrder.subList(preIndex + 1, inIndex + 1);
9+
List<Integer> prOrder = preOrder.subList(inIndex + 1, preOrder.size());
1110
12-
public static void levelOrder(List<List<Integer>> list, TreeNode node, int level) {
13-
if (node == null) {
14-
return;
15-
}
16-
if (list.size() < level + 1) {
17-
List<Integer> levelEle = new ArrayList<>();
18-
list.add(levelEle);
19-
}
20-
list.get(level).add(node.getVal());
21-
levelOrder(list, node.getLeft(), level + 1);
22-
levelOrder(list, node.getRight(), level + 1);
11+
List<Integer> ilOrder = inOrder.subList(0, inIndex);
12+
List<Integer> irOrder = inOrder.subList(inIndex + 1, inOrder.size());
13+
if (node == null) {
14+
node = new TreeNode(val, null, null);
15+
}
16+
TreeNode lnode = null,rnode = null;
17+
if (!plOrder.isEmpty()){
18+
lnode = new TreeNode(plOrder.get(0), null, null);
19+
}
20+
if (!prOrder.isEmpty()) {
21+
rnode = new TreeNode(prOrder.get(0), null, null);
22+
}
23+
node.setLeft(lnode);
24+
node.setRight(rnode);
25+
binaryTree(lnode, plOrder, ilOrder);
26+
binaryTree(rnode, prOrder, irOrder);
2327
}
28+
return node;
29+
}
2430
25-
public static void main(String[] args) {
26-
TreeNode r3r = new TreeNode(7, null, null);
27-
TreeNode r3l = new TreeNode(15, null, null);
28-
TreeNode l2r = new TreeNode(20, r3l, r3r);
29-
TreeNode l2l = new TreeNode(9, null, null);
30-
TreeNode root = new TreeNode(3, l2l, l2r);
31-
System.out.println(levelOrder(root));
32-
}
31+
public static void main(String[] args) {
32+
List<Integer> preOrder = new ArrayList<>();
33+
preOrder.add(1);
34+
preOrder.add(4);
35+
preOrder.add(6);
36+
preOrder.add(8);
37+
preOrder.add(9);
38+
preOrder.add(10);
39+
preOrder.add(11);
40+
List<Integer> inOrder = new ArrayList<>();
41+
inOrder.add(6);
42+
inOrder.add(4);
43+
inOrder.add(1);
44+
inOrder.add(9);
45+
inOrder.add(8);
46+
inOrder.add(10);
47+
inOrder.add(11);
48+
System.out.println(binaryTree(null, preOrder, inOrder));
49+
}
3350
}
3451
3552
@Data
3653
@AllArgsConstructor
3754
@NoArgsConstructor
55+
@ToString
3856
class TreeNode {
39-
private Integer val;
40-
private TreeNode left;
41-
private TreeNode right;
57+
private int val;
58+
private TreeNode left;
59+
private TreeNode right;
4260
}

0 commit comments

Comments
 (0)