Binary Tree Level Order Traversal II

import java.util.LinkedList; import java.util.List; import java.util.Queue; /* * 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,null,null,15,7], 3 / \ 9 20 / \ 15 7 return its bottom-up level order traversal as: [ [15,7], [9,20], [3] ] * */ public class Solution { public static void main(String[] args) { // TODO Auto-generated method stub } //采用DFS深度遍历 public List<List<Integer>> levelOrderBottom(TreeNode root) { Queue<TreeNode> que = new LinkedList<>(); List<List<Integer>> list = new LinkedList<List<Integer>>(); if(root == null) return list; que.offer(root);//先将根压入队列 while(!que.isEmpty()){//若队列不为空 int nodenums = que.size();//这一层共有多少个节点 List<Integer> subli = new LinkedList<>(); for(int i = 0;i<nodenums;i++)//对该层的每个节点进行遍历 { if(que.peek().left!=null)//去除队列尾部节点，判断左右节点是否为空，不为空则压入队列，等到下次遍历 que.offer(que.peek().left); if(que.peek().right!=null) que.offer(que.peek().right); subli.add(que.poll().val);//将该节点值加入到链表中 } list.add(0,subli);//将该层值以链表形式加入到外层链表中，并且按要求加入到链表的开头 } return list; } } class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } }