题目
二叉树的层次遍历 II
给出一棵二叉树，返回其节点值从底向上的层次序遍历（按从叶节点所在层到根节点所在的层遍历，然后逐层从左往右遍历）
样例
给出一棵二叉树 {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
按照从下往上的层次遍历为：
[
[15,7],
[9,20],
[3]
]
解题
和上一题的答案反过来
直接每次在list中第一个位置加入当前层结点
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/ public class Solution {
/**
* @param root: The root of binary tree.
* @return: buttom-up level order a list of lists of integer
*/
public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
// write your code here
ArrayList<ArrayList<Integer>> tree = new ArrayList<ArrayList<Integer>>();
if(root == null)
return tree;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){
ArrayList<Integer> list = new ArrayList<Integer>();
int size = queue.size();
for(int i = 0;i<size; i++){
TreeNode node = queue.poll();
list.add(node.val);
if(node.left!=null)
queue.offer(node.left);
if(node.right!=null)
queue.offer(node.right);
}
// add(index,list) list 插入到index位置
tree.add(0,list);
}
return tree;
}
}
Java Code