【LeetCode】 38二叉树的层序遍历
< 返回列表时间: 2020-05-27来源:OSCHINA
题目
给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
例如: 给定二叉树 [3,9,20,null,null,15,7]
示例: 给定的有序链表: [-10, -3, 0, 5, 9], 一个可能的答案是:[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树: 0 / -3 9 / / -10 5
返回其自底向上的层次遍历为: [ [15,7], [9,20], [3] ]
思路
本题和 102 题基本一致,区别就是每层的结点在二维数组中存放的先后顺序不同
前面所有代码都和 102 题一样,只需将最后存放位置每次都从 0 开始放就可以了
具体区别步骤写在代码注释处。
代码 /** * 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>> ans = new ArrayList<>(); if (root == null) { return ans; } Queue<TreeNode> q = new LinkedList<>(); q.add(root); while (!q.isEmpty()) { List<Integer> tmp = new ArrayList<>(); int len = q.size(); for (int i = 0; i < len; i++) { TreeNode node = q.poll(); tmp.add(node.val); if (node.left != null) { q.add(node.left); } if (node.right != null) { q.add(node.right); } } // 在索引 0 的位置加入一维数组 tmp // 每次新的数组进来都会被放在开始的位置 ans.add(0, tmp); } return ans; } }
热门排行