http://www.lintcode.com/en/problem/binary-tree-level-order-traversal/
题目：给定二叉树，按层级顺序输出。如：二叉树{3,9,20,#,#,15,7}
3 / \ 9 20 / \ 15 7
输出：
[ [3], [9,20], [15,7] ]
解答：首先判断根节点是否为空，为空直接返回。
将当前根节点放入队列中，当队列不为空时进行以下循环：
1.将队列头取出并记录其值；
2.建立新的arraylist，将取出元素的值放入list中（控制list的长度：queue.size() ）；
3.将当前取出的元素左右非空子节点加入队列中；
第一次犯错：未判断根节点为空的情况；
第二次犯错： queue.size()会动态变化，应在循环前取出并保存其值；
代码：
public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) { // write your code here ArrayList<ArrayList<Integer>> res = new ArrayList<>(); if (root == null) { return res; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()){ ArrayList<Integer> row = new ArrayList<>(); int size = queue.size(); for (int i = 0; i < size; i++) { TreeNode father = queue.poll(); row.add(father.val); if (father.left != null) { queue.offer(father.left); } if (father.right != null) { queue.offer(father.right); } } res.add(row); } return res; }
变题1：http://www.lintcode.com/en/problem/binary-tree-level-order-traversal-ii/
题目：同上，区别是从底层往上层输出；
解答：在以上代码返回前加上：Collections.reverse(res) 即可
变题2：http://www.lintcode.com/en/problem/binary-tree-zigzag-level-order-traversal/
题目：将二叉树按zigzag顺序输出，如：输入{3，9，20，6，#，15，7}，输出[ [3], [20, 9], [6,15, 7]；
解答：不再使用queue，使用两个stack来完成操作；
代码：
public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) { // write your code here ArrayList<ArrayList<Integer>> res = new ArrayList<>(); if (root == null) { return res; } Stack<TreeNode> stackCur = new Stack<>(); stackCur.push(root); boolean order = true; while (!stackCur.isEmpty()) { ArrayList<Integer> row = new ArrayList<>(); Stack<TreeNode> stackNext = new Stack<>(); while (!stackCur.isEmpty()) { TreeNode father = stackCur.pop(); row.add(father.val); if (order) { if (father.left != null) { stackNext.push(father.left); } if (father.right != null) { stackNext.push(father.right); } } else { if (father.right != null) { stackNext.push(father.right); } if (father.left != null) { stackNext.push(father.left); } } } res.add(row); order = !order; stackCur = stackNext; } return res; }
