Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
07/04/2017更新
前天周三洛心，覃超說(shuō)這題可以用DFS做站刑。就做了一下走贪。
精巧的地方在于res.get(level).add(node.val);這一句。按照DFS的思想考慮的話忘闻，它會(huì)把樹(shù)的每層最左邊節(jié)點(diǎn)存成一個(gè)cell list放到res里去，然后再backtracking回來(lái)，拿到那一level的節(jié)點(diǎn)繼續(xù)往響應(yīng)的leve 所在的cell list里面加婚脱。
如下：
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
dfs(res, root, 0);
return res;
}
private void dfs(List<List<Integer>> res, TreeNode node, int level) {
if (node == null) return;
if (level >= res.size()) {
res.add(new ArrayList<Integer>());
}
res.get(level).add(node.val);
dfs(res, node.left, level + 1);
dfs(res, node.right, level + 1);
}
初版
這題跟求Maximum depth of a binary的非遞歸方法非常像，用一個(gè)queue保存結(jié)點(diǎn)勺像。
Code Ganker的講解太好了：
這道題要求實(shí)現(xiàn)樹(shù)的層序遍歷障贸，其實(shí)本質(zhì)就是把樹(shù)看成一個(gè)有向圖，然后進(jìn)行一次廣度優(yōu)先搜索咏删，這個(gè)圖遍歷算法是非常常見(jiàn)的惹想，這里同樣是維護(hù)一個(gè)隊(duì)列，只是對(duì)于每個(gè)結(jié)點(diǎn)我們知道它的鄰接點(diǎn)只有可能是左孩子和右孩子督函，具體就不仔細(xì)介紹了嘀粱。算法的復(fù)雜度是就結(jié)點(diǎn)的數(shù)量，O(n)辰狡，空間復(fù)雜度是一層的結(jié)點(diǎn)數(shù)锋叨，也是O(n)。
public class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);
//本層結(jié)點(diǎn)數(shù)
int curNum = 1;
//下一層結(jié)點(diǎn)數(shù)
int nextNum = 0;
List<Integer> cell = new ArrayList<>();
while (!queue.isEmpty()) {
TreeNode temp = queue.poll();
curNum--;
cell.add(temp.val);
if (temp.left != null) {
queue.add(temp.left);
nextNum++;
}
if (temp.right != null) {
queue.add(temp.right);
nextNum++;
}
if (curNum == 0) {
res.add(cell);
curNum = nextNum;
nextNum = 0;
cell = new ArrayList<>();
}
}
return res;
}
注意不要把
List<Integer> cell = new ArrayList<>();寫(xiě)到while循環(huán)里宛篇，否則會(huì)出現(xiàn)下面的錯(cuò)誤娃磺。
Input:
[3,9,20,null,null,15,7]
Output:
[[3],[20],[7]]
Expected:
[[3],[9,20],[15,7]]
另外注意，queue要用poll方法取數(shù)而不是pop叫倍。
