二叉树的层次遍历II

题目链接描述示例初始代码模板代码

题目链接

https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/

描述

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

示例

给定二叉树 [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 返回其自底向上的层次遍历为： [ [15,7], [9,20], [3] ]

初始代码模板

/** * 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) { } }

代码

bfs求解，和普通的层次遍历差不多，直接从头插入就可以了

/** * 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) { List<List<Integer>> list = new LinkedList<>(); if (root == null) { return list; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { List<Integer> cur = new LinkedList<>(); for (int i = queue.size(); i > 0; i--) { TreeNode node = queue.poll(); cur.add(node.val); if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } list.add(0, cur); } return list; } }