題目
給你二叉樹的根節(jié)點(diǎn) root ，返回其節(jié)點(diǎn)值的 層序遍歷 戴尸。 （即逐層地罚拟，從左到右訪問所有節(jié)點(diǎn)）亿卤。
示例 1：
輸入：root = [3,9,20,null,null,15,7]
輸出：[[3],[9,20],[15,7]]
</pre>
示例 2：
輸入：root = [1]
輸出：[[1]]
示例 3：
輸入：root = []
輸出：[]
</pre>
提示：
- 樹中節(jié)點(diǎn)數(shù)目在范圍
[0, 2000]內(nèi) -1000 <= Node.val <= 1000
解題思路
這是一道典型的BFS題目喉酌，直接用隊(duì)列來實(shí)現(xiàn)即可热凹。
| 方法 | 時間復(fù)雜度 | 空間復(fù)雜度 |
|---|---|---|
| BFS | O(n) | O(n) |
Java代碼
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
if(root != null) queue.offer(root);
while(!queue.isEmpty()){
int size = queue.size();
List<Integer> list = new ArrayList<>();
for(int i = 0; i < size; i++){
TreeNode node = queue.poll();
list.add(node.val);
if(node.left != null) queue.offer(node.left);
if(node.right != null) queue.offer(node.right);
}
res.add(list);
}
return res;
}
}
總結(jié)
樹的遍歷有四種方式：
- 前序遍歷：DFS
- 中序遍歷：DFS
- 后序遍歷：DFS
- 層序遍歷：BFS
