199. 二叉树的右视图
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {// 存储每层的节点值List<List<Integer>> levels = new ArrayList<>();// 主方法：返回二叉树的右视图public List<Integer> rightSideView(TreeNode root) {List<Integer> result = new ArrayList<>(); // 存储最终的右视图// 边界条件判断，如果树为空，直接返回空数组if (root == null) {return result;}// 进行层序遍历，填充 levelshelper(root, 0);// 输出每层的节点值（用于调试）System.out.println(levels);// 获取每层最右边的值for (List<Integer> list : levels) {result.add(list.get(list.size() - 1)); // 将每层最后一个元素加入结果}return result; // 返回右视图的结果}// 递归辅助方法进行层序遍历public void helper(TreeNode root, int level) {// 如果当前层与 levels 数组的大小一致，表示需要新建一个列表来存储当前层的元素if (levels.size() == level) {levels.add(new ArrayList<>()); // 新建一个空列表}// 将当前节点的值加入对应层级的列表中levels.get(level).add(root.val);// 如果当前节点有左子树，继续递归到左子树，层级 +1if (root.left != null) {helper(root.left, level + 1);}// 如果当前节点有右子树，继续递归到右子树，层级 +1if (root.right != null) {helper(root.right, level + 1);} }}
637. 二叉树的层平均值
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {// 计算二叉树每一层节点值的平均值，并返回一个包含平均值的列表public List<Double> averageOfLevels(TreeNode root) {// 用于存储每一层节点的数量List<Integer> count = new ArrayList<>();// 用于存储每一层节点值的总和List<Double> sum = new ArrayList<>();// 调用深度优先搜索方法进行计算dfs(root, 0, count, sum);// 用于存储每一层的平均值List<Double> averages = new ArrayList<>();// 计算每一层的平均值并添加到 averages 列表中for (int i = 0; i < sum.size(); i++) {averages.add(sum.get(i) / count.get(i));}return averages;}// 深度优先搜索方法private void dfs(TreeNode root, Integer level, List<Integer> count, List<Double> sum) {// 如果根节点为空，直接返回if (root == null) {return;}// 如果当前层已经在 sums 和 counts 列表中有记录if (level < sum.size()) {// 更新当前层的节点值总和sum.set(level, sum.get(level) + root.val);// 更新当前层的节点数量count.set(level, count.get(level) + 1);} else {// 如果当前层是新的一层，添加新的总和和数量记录sum.add(root.val * 1.0);count.add(1);}// 递归搜索左子树dfs(root.right, level + 1, count, sum);// 递归搜索右子树dfs(root.left, level + 1, count, sum);}}
102. 二叉树的层序遍历
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {// 存储每层的节点值List<List<Integer>> levels = new ArrayList<>();// 主方法：返回二叉树的层序遍历结果public List<List<Integer>> levelOrder(TreeNode root) {// 如果根节点为空，直接返回 levels（会是空列表）if (root == null) {return levels;}// 调用辅助方法进行层序遍历helper(root, 0);// 返回层序遍历结果return levels;}// 递归辅助方法进行层序遍历public void helper(TreeNode root, Integer level) {// 如果当前层级与 levels 的大小一致，表示需要新建一个列表来存储当前层的节点if (levels.size() == level) {levels.add(new ArrayList<>()); // 新建一个空的子列表}// 将当前节点的值加入对应层的列表中levels.get(level).add(root.val);// 如果当前节点有左子节点，递归处理左子树，层级 +1if (root.left != null) {helper(root.left, level + 1);}// 如果当前节点有右子节点，递归处理右子树，层级 +1if (root.right != null) {helper(root.right, level + 1);}}}
103. 二叉树的锯齿形层序遍历
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public List<List<Integer>> zigzagLevelOrder(TreeNode root) {List<List<Integer>> ans = new ArrayList<>(); // 用于存放最终结果if (root == null) { // 如果根节点为空，返回空的结果return ans;}Queue<TreeNode> nodeQueue = new ArrayDeque<>(); // 初始化队列以进行层次遍历nodeQueue.offer(root); // 将根节点加入队列boolean isLeftOrder = true; // 标志变量，指示当前层的遍历顺序// 当队列不为空时，进行遍历while (!nodeQueue.isEmpty()) {Deque<Integer> levelList = new LinkedList<>(); // 使用双端队列存储当前层的节点值int size = nodeQueue.size(); // 记录当前层的节点数量// 遍历当前层的所有节点for (int i = 0; i < size; i++) {TreeNode curNode = nodeQueue.poll(); // 从队列中取出当前节点// 根据当前层的遍历顺序，决定如何添加节点值if (isLeftOrder) {levelList.offerLast(curNode.val); // 从尾部添加节点值（左到右）} else {levelList.offerFirst(curNode.val); // 从头部添加节点值（右到左）}// 将当前节点的左子节点加入队列if (curNode.left != null) {nodeQueue.offer(curNode.left);}// 将当前节点的右子节点加入队列if (curNode.right != null) {nodeQueue.offer(curNode.right);}}// 将当前层的值转换为列表并添加到结果集合中ans.add(new ArrayList<>(levelList));// 切换当前层的遍历顺序isLeftOrder = !isLeftOrder; // 反转顺序}return ans; // 返回包含锯齿形层次遍历的所有节点值的结果}
}
