Authored by Tony Feng
Created on April 17th, 2022
Last Modified on April 17th, 2022
Task 1 - Q32 - I. 从上到下打印二叉树
Question
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution: # BFS
def levelOrder(self, root: TreeNode) -> List[int]:
if not root:
return []
res, tmp = [], []
tmp.append(root)
while tmp: # Break until the queue is empty
node = tmp.pop(0)
res.append(node.val)
if node.left:
tmp.append(node.left)
if node.right:
tmp.append(node.right)
return res
|
Explanation
- Time Complexity: O(N)
- The algorithm needs to go through every node.
- Space Complexity: O(N)
- At most N/2 nodes are in the queue at the same time.
Task 2 - Q32 - II. 从上到下打印二叉树 II
Question
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
res, tmp = [], [root]
while tmp:
level = []
for _ in range(0, len(tmp)): # Tracing the number of nodes on each level
node = tmp.pop(0)
if node.left:
tmp.append(node.left)
if node.right:
tmp.append(node.right)
level.append(node.val)
res.append(level)
return res
|
Explanation
- Time Complexity: O(N)
- Space Complexity: O(N)
Task 3 - Q32 - III. 从上到下打印二叉树 III
Question
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
from collections import deque
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root: return []
res, tmp = [], [root]
while tmp:
level = deque()
for _ in range(len(tmp)):
node = tmp.pop(0)
if len(res) % 2 == 0: # res contains the traversed nodes
level.append(node.val) # level will contain the next level of nodes
else:
level.appendleft(node.val)
if node.left:
tmp.append(node.left)
if node.right:
tmp.append(node.right)
res.append(list(level))
return res
|
Explanation
- Time Complexity: O(N)
- Space Complexity: O(N)