Skip to content

Commit a99fde7

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.0103. Binary Tree Zigzag Level Order Traversal
1 parent 5855b5d commit a99fde7

File tree

4 files changed

+214
-58
lines changed

4 files changed

+214
-58
lines changed

‎solution/0100-0199/0103.Binary Tree Zigzag Level Order Traversal/README.md

Lines changed: 74 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -41,15 +41,87 @@
4141
<!-- 这里可写当前语言的特殊实现逻辑 -->
4242

4343
```python
44-
44+
# Definition for a binary tree node.
45+
# class TreeNode:
46+
# def __init__(self, val=0, left=None, right=None):
47+
# self.val = val
48+
# self.left = left
49+
# self.right = right
50+
class Solution:
51+
def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
52+
if root is None:
53+
return []
54+
res = []
55+
q = collections.deque([root])
56+
left = False
57+
while q:
58+
size = len(q)
59+
t = []
60+
for _ in range(size):
61+
node = q.popleft()
62+
t.append(node.val)
63+
if node.left:
64+
q.append(node.left)
65+
if node.right:
66+
q.append(node.right)
67+
if left:
68+
t.reverse()
69+
res.append(t)
70+
left = not left
71+
return res
4572
```
4673

4774
### **Java**
4875

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

5178
```java
52-
79+
/**
80+
* Definition for a binary tree node.
81+
* public class TreeNode {
82+
* int val;
83+
* TreeNode left;
84+
* TreeNode right;
85+
* TreeNode() {}
86+
* TreeNode(int val) { this.val = val; }
87+
* TreeNode(int val, TreeNode left, TreeNode right) {
88+
* this.val = val;
89+
* this.left = left;
90+
* this.right = right;
91+
* }
92+
* }
93+
*/
94+
class Solution {
95+
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
96+
if (root == null) {
97+
return Collections.emptyList();
98+
}
99+
Deque<TreeNode> q = new ArrayDeque<>();
100+
q.offer(root);
101+
List<List<Integer>> res = new ArrayList<>();
102+
boolean left = false;
103+
while (!q.isEmpty()) {
104+
int size = q.size();
105+
List<Integer> t = new ArrayList<>();
106+
while (size-- > 0) {
107+
TreeNode node = q.pollFirst();
108+
t.add(node.val);
109+
if (node.left != null) {
110+
q.offer(node.left);
111+
}
112+
if (node.right != null) {
113+
q.offer(node.right);
114+
}
115+
}
116+
if (left) {
117+
Collections.reverse(t);
118+
}
119+
res.add(t);
120+
left = !left;
121+
}
122+
return res;
123+
}
124+
}
53125
```
54126

55127
### **...**

‎solution/0100-0199/0103.Binary Tree Zigzag Level Order Traversal/README_EN.md

Lines changed: 74 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -44,13 +44,85 @@
4444
### **Python3**
4545

4646
```python
47-
47+
# Definition for a binary tree node.
48+
# class TreeNode:
49+
# def __init__(self, val=0, left=None, right=None):
50+
# self.val = val
51+
# self.left = left
52+
# self.right = right
53+
class Solution:
54+
def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
55+
if root is None:
56+
return []
57+
res = []
58+
q = collections.deque([root])
59+
left = False
60+
while q:
61+
size = len(q)
62+
t = []
63+
for _ in range(size):
64+
node = q.popleft()
65+
t.append(node.val)
66+
if node.left:
67+
q.append(node.left)
68+
if node.right:
69+
q.append(node.right)
70+
if left:
71+
t.reverse()
72+
res.append(t)
73+
left = not left
74+
return res
4875
```
4976

5077
### **Java**
5178

5279
```java
53-
80+
/**
81+
* Definition for a binary tree node.
82+
* public class TreeNode {
83+
* int val;
84+
* TreeNode left;
85+
* TreeNode right;
86+
* TreeNode() {}
87+
* TreeNode(int val) { this.val = val; }
88+
* TreeNode(int val, TreeNode left, TreeNode right) {
89+
* this.val = val;
90+
* this.left = left;
91+
* this.right = right;
92+
* }
93+
* }
94+
*/
95+
class Solution {
96+
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
97+
if (root == null) {
98+
return Collections.emptyList();
99+
}
100+
Deque<TreeNode> q = new ArrayDeque<>();
101+
q.offer(root);
102+
List<List<Integer>> res = new ArrayList<>();
103+
boolean left = false;
104+
while (!q.isEmpty()) {
105+
int size = q.size();
106+
List<Integer> t = new ArrayList<>();
107+
while (size-- > 0) {
108+
TreeNode node = q.pollFirst();
109+
t.add(node.val);
110+
if (node.left != null) {
111+
q.offer(node.left);
112+
}
113+
if (node.right != null) {
114+
q.offer(node.right);
115+
}
116+
}
117+
if (left) {
118+
Collections.reverse(t);
119+
}
120+
res.add(t);
121+
left = !left;
122+
}
123+
return res;
124+
}
125+
}
54126
```
55127

56128
### **...**

‎solution/0100-0199/0103.Binary Tree Zigzag Level Order Traversal/Solution.java

Lines changed: 41 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -1,21 +1,46 @@
1+
/**
2+
* Definition for a binary tree node.
3+
* public class TreeNode {
4+
* int val;
5+
* TreeNode left;
6+
* TreeNode right;
7+
* TreeNode() {}
8+
* TreeNode(int val) { this.val = val; }
9+
* TreeNode(int val, TreeNode left, TreeNode right) {
10+
* this.val = val;
11+
* this.left = left;
12+
* this.right = right;
13+
* }
14+
* }
15+
*/
116
class Solution {
2-
private List<List<Integer>> list;
317
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
4-
list = new ArrayList<>();
5-
lever(root, 0);
6-
for (int i = 1; i < list.size(); i = i + 2) {
7-
List<Integer> nList = list.get(i);
8-
List<Integer> nnl = new ArrayList<>();
9-
for (int j = nList.size() - 1; j >= 0; j--) nnl.add(nList.get(j));
10-
list.set(i, nnl);
18+
if (root == null) {
19+
return Collections.emptyList();
1120
}
12-
return list;
13-
}
14-
private void lever(TreeNode root, int l) {
15-
if (root == null) return;
16-
while (l > list.size() - 1) list.add(new ArrayList<>());
17-
list.get(l++).add(root.val);
18-
lever(root.left, l);
19-
lever(root.right, l);
21+
Deque<TreeNode> q = new ArrayDeque<>();
22+
q.offer(root);
23+
List<List<Integer>> res = new ArrayList<>();
24+
boolean left = false;
25+
while (!q.isEmpty()) {
26+
int size = q.size();
27+
List<Integer> t = new ArrayList<>();
28+
while (size-- > 0) {
29+
TreeNode node = q.pollFirst();
30+
t.add(node.val);
31+
if (node.left != null) {
32+
q.offer(node.left);
33+
}
34+
if (node.right != null) {
35+
q.offer(node.right);
36+
}
37+
}
38+
if (left) {
39+
Collections.reverse(t);
40+
}
41+
res.add(t);
42+
left = !left;
43+
}
44+
return res;
2045
}
2146
}

‎solution/0100-0199/0103.Binary Tree Zigzag Level Order Traversal/Solution.py

Lines changed: 25 additions & 38 deletions
Original file line numberDiff line numberDiff line change
@@ -1,41 +1,28 @@
11
# Definition for a binary tree node.
2-
# class TreeNode(object):
3-
# def __init__(self, x):
4-
# self.val = x
5-
# self.left = None
6-
# self.right = None
7-
8-
9-
class Solution(object):
10-
def zigzagLevelOrder(self, root):
11-
"""
12-
:type root: TreeNode
13-
:rtype: List[List[int]]
14-
"""
15-
zuo = []
16-
you = []
2+
# class TreeNode:
3+
# def __init__(self, val=0, left=None, right=None):
4+
# self.val = val
5+
# self.left = left
6+
# self.right = right
7+
class Solution:
8+
def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
179
if root is None:
1810
return []
19-
zuo.append(root)
20-
ans = []
21-
while zuo or you:
22-
tmp = []
23-
while zuo:
24-
if zuo[0].left is not None:
25-
you.append(zuo[0].left)
26-
if zuo[0].right is not None:
27-
you.append(zuo[0].right)
28-
tmp.append(zuo[0].val)
29-
zuo.pop(0)
30-
ans.append(tmp)
31-
tmp = []
32-
while you:
33-
if you[-1].right is not None:
34-
zuo.insert(0, you[-1].right)
35-
if you[-1].left is not None:
36-
zuo.insert(0, you[-1].left)
37-
tmp.append(you[-1].val)
38-
you.pop(-1)
39-
if tmp:
40-
ans.append(tmp)
41-
return ans
11+
res = []
12+
q = collections.deque([root])
13+
left = False
14+
while q:
15+
size = len(q)
16+
t = []
17+
for _ in range(size):
18+
node = q.popleft()
19+
t.append(node.val)
20+
if node.left:
21+
q.append(node.left)
22+
if node.right:
23+
q.append(node.right)
24+
if left:
25+
t.reverse()
26+
res.append(t)
27+
left = not left
28+
return res

0 commit comments

Comments
 (0)