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] ]
传送门：https://leetcode.com/problems/binary-tree-level-order-traversal-ii/
题目和第102题很像，只要把队列改成栈，逆序输出即可。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List<List<Integer>> levelOrderBottom(TreeNode root) { //创建要返回的列表存放所有节点值 List<List<Integer>> list = new LinkedList<List<Integer>>(); //创建一个栈存放各层全部的节点值 if(root == null) return list; Stack<List<Integer>> slist = new Stack<List<Integer>>(); //创建一个栈存放一层的节点 Queue<TreeNode> currentLevel = new LinkedList<TreeNode>(); //先把根节点压入栈中 currentLevel.add(root); while(!currentLevel.isEmpty()) { int size = currentLevel.size(); //创建列表存放某一层的所有节点值 List<Integer> currentList = new LinkedList<Integer>(); for(int i = 0; i < size; i++) { TreeNode currentNode = currentLevel.poll(); currentList.add(currentNode.val); if(currentNode.left != null) currentLevel.add(currentNode.left); if(currentNode.right != null) currentLevel.add(currentNode.right); } slist.push(currentList); } while(!slist.isEmpty()) list.add(slist.pop()); return list; } }
Leetcode-107(Java) Binary Tree Level Order Traversal II
原文：http://www.cnblogs.com/zetrov/p/4699582.html