Given a binary tree, return the bottom-up level order traversal of its nodes‘ values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree {3,9,20,#,#,15,7},
3
/ 9 20
/ 15 7
return its bottom-up level order traversal as:
[ [15,7], [9,20], [3] ]
题目大意为，按照层次逆序输出每一层的节点，很明显用层次遍历即可，之前在Minimum Depth of Binary Tree ——LeetCode这个题目中，也用到了层次遍历，下面先看我写的，也是用upRow，downRow，来记录上一层、下一层的节点数量，upRow--为0时，一层遍历完了。
public List<List<Integer>> levelOrderBottom(TreeNode root) { List<Integer> level = new LinkedList<>(); List<List<Integer>> res = new LinkedList<>(); if (root == null) return res; ArrayDeque<TreeNode> queue = new ArrayDeque<>(); queue.add(root); int upRow = 1, downRow = 0; while (!queue.isEmpty()) { TreeNode node = queue.getFirst(); queue.removeFirst(); if (node.left != null) { queue.add(node.left); downRow++; } if (node.right != null) { queue.add(node.right); downRow++; } upRow--; level.add(node.val); if (upRow == 0) { res.add(0, level); level = new LinkedList<>(); upRow = downRow; downRow=0; } } return res; }
后来发现一种更巧妙的解，就是利用queue的size()，根本不用记录这两个值。
Talk is cheap>>
public List<List<Integer>> levelOrderBottom2(TreeNode root) { Queue<TreeNode> queue = new LinkedList<>(); List<List<Integer>> wrapList = new LinkedList<>(); if (root == null) return wrapList; queue.offer(root); while (!queue.isEmpty()) { int levelNum = queue.size(); List<Integer> subList = new LinkedList<>();
//把一层元素全部取出 for (int i = 0; i < levelNum; i++) { TreeNode node = queue.poll();//取出队列第一个元素 if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); subList.add(node.val); } wrapList.add(0, subList); } return wrapList; }
Binary Tree Level Order Traversal II——LeetCode
原文：http://www.cnblogs.com/aboutblank/p/4357251.html