【Leetcode】107. 二叉树的层次遍历 II

题目给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）例如：给定二叉树 [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7返回其自底向上的层次遍历为：[ [15,7], [9,20], [3]]题解利用层次遍历,层次遍历的时候进入下一层的时候记录一下当前队列中有几个元素。class Solution { public List<List<Integer>> levelOrderBottom(TreeNode root) { List<List<Integer>> res = new LinkedList<>(); if (root == null) { return res; } LinkedList<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { int size = queue.size(); List<Integer> levelVal = new LinkedList<>(); while (size > 0) { TreeNode current = queue.poll(); if (current.left != null) { queue.add(current.left); } if (current.right != null) { queue.add(current.right); } levelVal.add(current.val); size–; } res.add(0, levelVal); } return res; }}用递归去做。用递归去做的关键在于需要把层数也带上。class Solution { public List<List<Integer>> levelOrderBottom(TreeNode root) { List<List<Integer>> res = new LinkedList<>(); if (root == null) { return res; } helper(root, res, 0); return res; } public void helper(TreeNode root, List<List<Integer>> res, int depth) { if (root == null) { return; } if (depth == res.size()) { res.add(0, new LinkedList<>()); } List<Integer> current = res.get(res.size() - depth - 1); helper(root.left, res, depth + 1); helper(root.right, res, depth + 1); current.add(root.val); }}热门阅读技术文章汇总【Leetcode】103. 二叉树的锯齿形层次遍历【Leetcode】102. 二叉树的层次遍历【Leetcode】101. 对称二叉树【Leetcode】100. 相同的树【Leetcode】98. 验证二叉搜索树手撕代码QQ群：805423079， 群密码：1024