107. 二叉树的层次遍历 II

题目描述

给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

例如： 给定二叉树 [3,9,20,null,null,15,7],

3 / \ 9 20 / \ 15 7

返回其自底向上的层次遍历为：

[ [15,7], [9,20], [3] ]

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的思路

思路一（偷懒）

利用102. 二叉树的层次遍历（没做过这道题的可以先看这道题，两道题目类似），在return语句之前将列表反转即可得到最后的答案。

思路二

还是从上面到下面，一层一层遍历，但是每遍历一层，该层数值对应的列表要添加到大列表的开头。调用list.addFirst(shortList);或list.add(0, shortList);，即可在列表开头插入元素。

我的程序

程序一（偷懒）

参考了别人写的代码，部分进行了优化：

import java.util.*; /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<List<Integer>> levelOrderBottom(TreeNode root) { if(root == null) return new LinkedList<>(); List<List<Integer>> list = new LinkedList<>(); // 初始化大的列表 Queue<TreeNode> queue = new LinkedList<TreeNode>(); // 初始化队列，用于存储树的结点 queue.offer(root); while(!queue.isEmpty()){ List<Integer> shortList = new LinkedList<Integer>(); int count = queue.size(); // 当前层结点数 while(count != 0){ // 把队列中当前层的元素取光为止 TreeNode node = queue.poll(); // 取出队首的结点 shortList.add(node.val); // 把该结点中的值添加到小列表中 count--; // 当前层访问完一个结点，数量减一 if(node.left != null) // 当前访问结点有左子结点 queue.offer(node.left); // 则把该左子结点添加到队尾 // 因为层序遍历在每一层都是从左到右的，队列是先进先出，所以先存左子结点，然后再右子结点 if(node.right != null)// 当前访问结点有右子结点 queue.offer(node.right); // 则把该右子结点添加到队尾 } list.add(shortList); // 把当前层的元素列表添加到大列表中 } Collections.reverse(list); // 反转列表 return list; } }

程序二

import java.util.*; class Solution { public List<List<Integer>> levelOrderBottom(TreeNode root) { LinkedList<List<Integer>> list = new LinkedList<>(); // 初始化大的列表 if(root == null) return list; Queue<TreeNode> queue = new LinkedList<TreeNode>(); // 初始化队列，用于存储树的结点 queue.offer(root); while(!queue.isEmpty()){ List<Integer> shortList = new LinkedList<Integer>(); int count = queue.size(); // 当前层结点数 while(count != 0){ // 把队列中当前层的元素取光为止 TreeNode node = queue.poll(); // 取出队首的结点 shortList.add(node.val); // 把该结点中的值添加到小列表中 count--; // 当前层访问完一个结点，数量减一 if(node.left != null) // 当前访问结点有左子结点 queue.offer(node.left); // 则把该左子结点添加到队尾 // 因为层序遍历在每一层都是从左到右的，队列是先进先出，所以先存左子结点，然后再右子结点 if(node.right != null)// 当前访问结点有右子结点 queue.offer(node.right); // 则把该右子结点添加到队尾 } list.addFirst(shortList); // 把当前层的元素列表添加到大列表中 // list.add(0, shortList); // 用这个也可以 } return list; } }

如有不当之处，欢迎读者批评指正！