Problem
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,#,#,15,7}, 3 / \ 9 20 / \ 15 7
return its level order traversal as:
[ [3], [9,20], [15,7]]
Note
用先入先出的Queue。用size标记每一层的结点数目并定向循环。
Solution
class Solution { public List > levelOrder(TreeNode root) { List > res = new ArrayList<>(); if (root == null) return res; Queue queue = new LinkedList (); queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); List temp = new ArrayList<>(); for (int i = 0; i < size; i++) { TreeNode cur = queue.poll(); if (cur.left != null) queue.offer(cur.left); if (cur.right != null) queue.offer(cur.right); temp.add(cur.val); } res.add(temp);//for traversal II: res.add(0, temp); } return res; }}
DFS
class Solution { public List > levelOrder(TreeNode root) { List > res = new ArrayList<>(); dfs(root, 0, res); return res; } private void dfs(TreeNode root, int level, List > res) { if (root == null) return; if (level >= res.size()) res.add(new ArrayList ()); //level >= res.size() ---- from 0 >= 0 to initialize res.get(level).add(root.val); dfs(root.left, level+1, res); dfs(root.right, level+1, res); }}
From bottom
public class Solution { public ArrayList > levelOrderBottom(TreeNode root) { ArrayList > res = new ArrayList<>(); if (root == null) return res; helper(root, res, 0); return res; } public void helper(TreeNode root, ArrayList > res, int index) { int size = res.size(); if (index == size) { ArrayList curList = new ArrayList<>(); curList.add(root.val); res.add(0, curList); } else res.get(size-index-1).add(root.val); if (root.left != null) helper(root.left, res, index+1); if (root.right != null) helper(root.right, res, index+1); }}