数据结构——二叉树层序遍历

107. 二叉树的层序遍历 II

107. 二叉树的层序遍历 II

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

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[15,7],[9,20],[3]]

自底向上遍历，将原层序遍历的结果反转即可

class Solution {public List<List<Integer>> levelOrderBottom(TreeNode root) {List<List<Integer>> list = new ArrayList<>();Deque<TreeNode> que = new LinkedList<>();if (root == null) {return list;}que.offer(root);while (!que.isEmpty()) {List<Integer> itemList = new ArrayList<Integer>();int len = que.size();while (len > 0) {TreeNode tmpNode = que.poll();itemList.add(tmpNode.val);if (tmpNode.left != null) que.offer(tmpNode.left);if (tmpNode.right != null) que.offer(tmpNode.right);len--;}list.add(itemList);}List<List<Integer>> result = new ArrayList<>();for (int i = list.size() - 1; i >= 0; i-- ) {result.add(list.get(i));}return result;}
}

199. 二叉树的右视图

199. 二叉树的右视图
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例 1:

输入: [1,2,3,null,5,null,4]
输出: [1,3,4]

思路：

层序遍历的时候，判断是否遍历到单层的最后面的元素，如果是，就放进result数组中，随后返回result就可以了。

class Solution {public List<Integer> rightSideView(TreeNode root) {List<Integer> list = new ArrayList<>();Deque<TreeNode> que = new LinkedList<>();if (root == null) {return list;}que.offerLast(root);while (!que.isEmpty()) {int levelSize = que.size();for (int i = 0; i < levelSize; i++) {TreeNode poll = que.pollFirst();if (poll.left != null) {que.addLast(poll.left);}if (poll.right != null) {que.addLast(poll.right);}if (i == levelSize - 1) {list.add(poll.val);}}}return list;}
}

637. 二叉树的层平均值

637. 二叉树的层平均值

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。
在这里插入图片描述

层序遍历的时候把一层求个总和在取一个均值。

class Solution {public List<Double> averageOfLevels(TreeNode root) {List<Double> list = new ArrayList<>();Deque<TreeNode> que = new LinkedList<>();if (root==null){return list;}que.offerLast(root);while(!que.isEmpty()){TreeNode peek = que.peekFirst();int levelSize = que.size();double levelSum = 0.0;// 统计每一层的和for (int i = 0; i < levelSize; i++) {TreeNode poll = que.pollFirst();levelSum += poll.val;if (poll.left != null) {que.addLast(poll.left);}if (poll.right != null) {que.addLast(poll.right);}}list.add(levelSum / levelSize);//均值放入结果list}return list;}
}