Skip to content

Commit 8f34b0a

Browse files
yanglbmeyanglbme
committed
feat: add solutions to leetcode problem: No.0107
See https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/
1 parent 55530e1 commit 8f34b0a

File tree

6 files changed

+164
-22
lines changed

6 files changed

+164
-22
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -85,6 +85,7 @@
8585

8686
1. [对称二叉树](/solution/0100-0199/0101.Symmetric%20Tree/README.md)
8787
1. [二叉树的层次遍历](/solution/0100-0199/0102.Binary%20Tree%20Level%20Order%20Traversal/README.md)
88+
1. [二叉树的层次遍历 II](/solution/0100-0199/0107.Binary%20Tree%20Level%20Order%20Traversal%20II/README.md)
8889
1. [二叉树的最大深度](/solution/0100-0199/0104.Maximum%20Depth%20of%20Binary%20Tree/README.md)
8990
1. [从前序与中序遍历序列构造二叉树](/solution/0100-0199/0105.Construct%20Binary%20Tree%20from%20Preorder%20and%20Inorder%20Traversal/README.md)
9091
1. [从中序与后序遍历序列构造二叉树](/solution/0100-0199/0106.Construct%20Binary%20Tree%20from%20Inorder%20and%20Postorder%20Traversal/README.md)

‎README_EN.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -83,6 +83,7 @@ Complete solutions to [LeetCode](https://leetcode-cn.com/problemset/all/), [LCOF
8383

8484
1. [Symmetric Tree](/solution/0100-0199/0101.Symmetric%20Tree/README_EN.md)
8585
1. [Binary Tree Level Order Traversal](/solution/0100-0199/0102.Binary%20Tree%20Level%20Order%20Traversal/README_EN.md)
86+
1. [Binary Tree Level Order Traversal II](/solution/0100-0199/0107.Binary%20Tree%20Level%20Order%20Traversal%20II/README_EN.md)
8687
1. [Maximum Depth of Binary Tree](/solution/0100-0199/0104.Maximum%20Depth%20of%20Binary%20Tree/README_EN.md)
8788
1. [Construct Binary Tree from Preorder and Inorder Traversal](/solution/0100-0199/0105.Construct%20Binary%20Tree%20from%20Preorder%20and%20Inorder%20Traversal/README_EN.md)
8889
1. [Construct Binary Tree from Inorder and Postorder Traversal](/solution/0100-0199/0106.Construct%20Binary%20Tree%20from%20Inorder%20and%20Postorder%20Traversal/README_EN.md)

‎solution/0100-0199/0107.Binary Tree Level Order Traversal II/README.md

Lines changed: 57 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -30,22 +30,77 @@
3030

3131
<!-- 这里可写通用的实现逻辑 -->
3232

33+
同 [102](/solution/0100-0199/0102.Binary%20Tree%20Level%20Order%20Traversal/README.md)，最后反转一下结果即可。
34+
3335
<!-- tabs:start -->
3436

3537
### **Python3**
3638

3739
<!-- 这里可写当前语言的特殊实现逻辑 -->
3840

3941
```python
40-
42+
# Definition for a binary tree node.
43+
# class TreeNode:
44+
# def __init__(self, x):
45+
# self.val = x
46+
# self.left = None
47+
# self.right = None
48+
49+
class Solution:
50+
def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
51+
if root is None:
52+
return []
53+
q = [root]
54+
res = []
55+
while q:
56+
size = len(q)
57+
t = []
58+
for _ in range(size):
59+
node = q.pop(0)
60+
t.append(node.val)
61+
if node.left is not None:
62+
q.append(node.left)
63+
if node.right is not None:
64+
q.append(node.right)
65+
res.append(t)
66+
return res[::-1]
4167
```
4268

4369
### **Java**
4470

4571
<!-- 这里可写当前语言的特殊实现逻辑 -->
4672

4773
```java
48-
74+
/**
75+
* Definition for a binary tree node.
76+
* public class TreeNode {
77+
* int val;
78+
* TreeNode left;
79+
* TreeNode right;
80+
* TreeNode(int x) { val = x; }
81+
* }
82+
*/
83+
class Solution {
84+
public List<List<Integer>> levelOrderBottom(TreeNode root) {
85+
if (root == null) return Collections.emptyList();
86+
Deque<TreeNode> q = new ArrayDeque<>();
87+
q.offer(root);
88+
List<List<Integer>> res = new ArrayList<>();
89+
while (!q.isEmpty()) {
90+
int size = q.size();
91+
List<Integer> t = new ArrayList<>();
92+
while (size-- > 0) {
93+
TreeNode node = q.poll();
94+
t.add(node.val);
95+
if (node.left != null) q.offer(node.left);
96+
if (node.right != null) q.offer(node.right);
97+
}
98+
res.add(t);
99+
}
100+
Collections.reverse(res);
101+
return res;
102+
}
103+
}
49104
```
50105

51106
### **...**

‎solution/0100-0199/0107.Binary Tree Level Order Traversal II/README_EN.md

Lines changed: 55 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -55,13 +55,66 @@ return its bottom-up level order traversal as:<br />
5555
### **Python3**
5656

5757
```python
58-
58+
# Definition for a binary tree node.
59+
# class TreeNode:
60+
# def __init__(self, x):
61+
# self.val = x
62+
# self.left = None
63+
# self.right = None
64+
65+
class Solution:
66+
def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
67+
if root is None:
68+
return []
69+
q = [root]
70+
res = []
71+
while q:
72+
size = len(q)
73+
t = []
74+
for _ in range(size):
75+
node = q.pop(0)
76+
t.append(node.val)
77+
if node.left is not None:
78+
q.append(node.left)
79+
if node.right is not None:
80+
q.append(node.right)
81+
res.append(t)
82+
return res[::-1]
5983
```
6084

6185
### **Java**
6286

6387
```java
64-
88+
/**
89+
* Definition for a binary tree node.
90+
* public class TreeNode {
91+
* int val;
92+
* TreeNode left;
93+
* TreeNode right;
94+
* TreeNode(int x) { val = x; }
95+
* }
96+
*/
97+
class Solution {
98+
public List<List<Integer>> levelOrderBottom(TreeNode root) {
99+
if (root == null) return Collections.emptyList();
100+
Deque<TreeNode> q = new ArrayDeque<>();
101+
q.offer(root);
102+
List<List<Integer>> res = new ArrayList<>();
103+
while (!q.isEmpty()) {
104+
int size = q.size();
105+
List<Integer> t = new ArrayList<>();
106+
while (size-- > 0) {
107+
TreeNode node = q.poll();
108+
t.add(node.val);
109+
if (node.left != null) q.offer(node.left);
110+
if (node.right != null) q.offer(node.right);
111+
}
112+
res.add(t);
113+
}
114+
Collections.reverse(res);
115+
return res;
116+
}
117+
}
65118
```
66119

67120
### **...**

‎solution/0100-0199/0107.Binary Tree Level Order Traversal II/Solution.java

Lines changed: 25 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -1,23 +1,30 @@
1+
/**
2+
* Definition for a binary tree node.
3+
* public class TreeNode {
4+
* int val;
5+
* TreeNode left;
6+
* TreeNode right;
7+
* TreeNode(int x) { val = x; }
8+
* }
9+
*/
110
class Solution {
2-
List<List<Integer>> lists;
311
public List<List<Integer>> levelOrderBottom(TreeNode root) {
4-
lists = new ArrayList<>();
5-
levelOrderBottom(root,0);
6-
List<List<Integer>> result = new ArrayList<>();
7-
for (int i = lists.size() - 1; i >= 0; i--) result.add(lists.get(i));
8-
return result;
9-
}
10-
private void levelOrderBottom(TreeNode root, int i) {
11-
if (root==null) return;
12-
List<Integer> list;
13-
if (i==lists.size()){
14-
list = new ArrayList<>();
15-
lists.add(list);
16-
}else {
17-
list = lists.get(i);
12+
if (root == null) return Collections.emptyList();
13+
Deque<TreeNode> q = new ArrayDeque<>();
14+
q.offer(root);
15+
List<List<Integer>> res = new ArrayList<>();
16+
while (!q.isEmpty()) {
17+
int size = q.size();
18+
List<Integer> t = new ArrayList<>();
19+
while (size-- > 0) {
20+
TreeNode node = q.poll();
21+
t.add(node.val);
22+
if (node.left != null) q.offer(node.left);
23+
if (node.right != null) q.offer(node.right);
24+
}
25+
res.add(t);
1826
}
19-
list.add(root.val);
20-
levelOrderBottom(root.left,i+1);
21-
levelOrderBottom(root.right,i+1);
27+
Collections.reverse(res);
28+
return res;
2229
}
2330
}

‎solution/0100-0199/0107.Binary Tree Level Order Traversal II/Solution.py

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
# Definition for a binary tree node.
2+
# class TreeNode:
3+
# def __init__(self, x):
4+
# self.val = x
5+
# self.left = None
6+
# self.right = None
7+
8+
class Solution:
9+
def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
10+
if root is None:
11+
return []
12+
q = [root]
13+
res = []
14+
while q:
15+
size = len(q)
16+
t = []
17+
for _ in range(size):
18+
node = q.pop(0)
19+
t.append(node.val)
20+
if node.left is not None:
21+
q.append(node.left)
22+
if node.right is not None:
23+
q.append(node.right)
24+
res.append(t)
25+
return res[::-1]

0 commit comments

Comments
 (0)