Given a binary tree, return the?level order?traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree?[3,9,20,null,null,15,7],

3/ \9 20/ \15 7

?

return its level order traversal as:

[[3],[9,20],[15,7] ]

這個題目非常明顯的適用BFS, 從root, 依次將每一層append進入ans里, 只是要注意的就是如果判斷哪個是在哪一層呢, 這里用到的方法是利用size of queue, 每次得到的size就是該層的數目,
每層用一個temp list去存每一層的元素, 結束之后append進入ans中.


1. Constraints
1) tree 可以為empty, 所以edge case 為root == None

2. Ideas

BFS T: O(n) S: O(n) n is number of nodes in the tree


3. code import collections class Solution:def levelOrder(self, root):""":type root: TreeNode:rtype: List[List[int]]"""if not root: return []ans, queue = [], collections.deque([root])while queue:size, level = len(queue), []for _ in range(size):node = queue.popleft()level.append(node.val)if node.left:queue.append(node.left)if node.right:queue.append(node.right)ans.append(level)return ans

?

?

4. Test cases

1) None? ?=>? ?[]

2) [1]? ? =>? [[1]]

3)?

Given binary tree?[3,9,20,null,null,15,7],

3/ \9 20/ \15 7

?

return its level order traversal as:

[[3],[9,20],[15,7] ]

轉載于:https://www.cnblogs.com/Johnsonxiong/p/9261520.html

總結

以上是生活随笔為你收集整理的[LeetCode] 102. Binary Tree Level Order Traversal_Medium tag: BFS的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。