- 描述
Given a binary tree, return the level order traversal of its nodes’ values.
For example: Given binary tree {3,9,20,#,#,15,7}, return
[
[3],
[9,20],
[15,7]
]
- 分析
不需要保存具體層的很簡單贬媒，參考廣度優(yōu)先搜索BFS思想觉壶，只需要一個輔助隊列拌滋，本題需要兩個輔助隊列是鬼，一個保存0層的節(jié)點，一個保存1層的節(jié)點（也就是0層的下層節(jié)點）变泄，當0層節(jié)點的隊列出隊完畢秋麸，那么1層隊列也填滿，交換兩個隊列膀钠，掃描1層的下層節(jié)點掏湾，也就是2層，如此循環(huán)下去肿嘲，直到最下層葉子掃描完畢融击。
- 時間復雜度O(n)，空間復雜度O(n)
import java.util.*;
public class Solution {
public List<List<Integer>> levelOrderTraverse(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if(root == null)
return result;
Queue<TreeNode> rootQueue = new LinkedList<>();
Queue<TreeNode> leafQueue = new LinkedList<>();
rootQueue.add(root);
while(!rootQueue.isEmpty()) {
List<Integer> levelRes = new ArrayList<>();
while(!rootQueue.isEmpty()) {
TreeNode p = rootQueue.poll();
levelRes.add(p.val);
if(p.left != null) leafQueue.add(p.left);
if(p.right != null) leafQueue.add(p.right);
}
result.add(levelRes);
// 交換上層和下層的隊列
Queue<TreeNode> tmp = rootQueue;
rootQueue = leafQueue;
leafQueue = tmp;
}
return result;
}
}
