LeetCode之二叉树层次遍历

199. 二叉树的右视图

1. /**
2. * Definition for a binary tree node.
3. * public class TreeNode {
4. *     int val;
5. *     TreeNode left;
6. *     TreeNode right;
7. *     TreeNode() {}
8. *     TreeNode(int val) { this.val = val; }
9. *     TreeNode(int val, TreeNode left, TreeNode right) {
10. *         this.val = val;
11. *         this.left = left;
12. *         this.right = right;
13. *     }
14. * }
15. */
16. class Solution {
18.     // 存储每层的节点值
19.     List<List<Integer>> levels = new ArrayList<>();
21.     // 主方法：返回二叉树的右视图
22.     public List<Integer> rightSideView(TreeNode root) {
23.         List<Integer> result = new ArrayList<>(); // 存储最终的右视图
24.         // 边界条件判断，如果树为空，直接返回空数组
25.         if (root == null) {
26.             return result;
27.         }
28.         // 进行层序遍历，填充 levels
29.         helper(root, 0);
30.         // 输出每层的节点值（用于调试）
31.         System.out.println(levels);
32.         
33.         // 获取每层最右边的值
34.         for (List<Integer> list : levels) {
35.             result.add(list.get(list.size() - 1)); // 将每层最后一个元素加入结果
36.         }
37.         return result; // 返回右视图的结果
38.     }
40.     // 递归辅助方法进行层序遍历
41.     public void helper(TreeNode root, int level) {
42.         // 如果当前层与 levels 数组的大小一致，表示需要新建一个列表来存储当前层的元素
43.         if (levels.size() == level) {
44.             levels.add(new ArrayList<>()); // 新建一个空列表
45.         }
46.         // 将当前节点的值加入对应层级的列表中
47.         levels.get(level).add(root.val);
49.         // 如果当前节点有左子树，继续递归到左子树，层级 +1
50.         if (root.left != null) {
51.             helper(root.left, level + 1);
52.         }
53.         // 如果当前节点有右子树，继续递归到右子树，层级 +1
54.         if (root.right != null) {
55.             helper(root.right, level + 1);
56.         }     
57.     }
59. }

复制代码

637. 二叉树的层平均值

1. /**
2. * Definition for a binary tree node.
3. * public class TreeNode {
4. *     int val;
5. *     TreeNode left;
6. *     TreeNode right;
7. *     TreeNode() {}
8. *     TreeNode(int val) { this.val = val; }
9. *     TreeNode(int val, TreeNode left, TreeNode right) {
10. *         this.val = val;
11. *         this.left = left;
12. *         this.right = right;
13. *     }
14. * }
15. */
16. class Solution {
18.     // 计算二叉树每一层节点值的平均值，并返回一个包含平均值的列表
19.     public List<Double> averageOfLevels(TreeNode root) {
20.         // 用于存储每一层节点的数量
21.         List<Integer> count = new ArrayList<>();
22.         // 用于存储每一层节点值的总和
23.         List<Double> sum = new ArrayList<>();
24.         // 调用深度优先搜索方法进行计算
25.         dfs(root, 0, count, sum);
26.         // 用于存储每一层的平均值
27.         List<Double> averages = new ArrayList<>();
28.         // 计算每一层的平均值并添加到 averages 列表中
29.         for (int i = 0; i < sum.size(); i++) {
30.             averages.add(sum.get(i) / count.get(i));
31.         }
33.         return averages;
34.     }
36.     // 深度优先搜索方法
37.     private void dfs(TreeNode root, Integer level, List<Integer> count, List<Double> sum) {
38.         // 如果根节点为空，直接返回
39.         if (root == null) {
40.             return;
41.         }
42.         // 如果当前层已经在 sums 和 counts 列表中有记录
43.         if (level < sum.size()) {
44.             // 更新当前层的节点值总和
45.             sum.set(level, sum.get(level) + root.val);
46.             // 更新当前层的节点数量
47.             count.set(level, count.get(level) + 1);
48.         } else {
49.             // 如果当前层是新的一层，添加新的总和和数量记录
50.             sum.add(root.val * 1.0);
51.             count.add(1);
52.         }
54.         // 递归搜索左子树
55.         dfs(root.right, level + 1, count, sum);
56.         // 递归搜索右子树
57.         dfs(root.left, level + 1, count, sum);
58.     }
60. }

复制代码

102. 二叉树的层序遍历

1. /**
2. * Definition for a binary tree node.
3. * public class TreeNode {
4. *     int val;
5. *     TreeNode left;
6. *     TreeNode right;
7. *     TreeNode() {}
8. *     TreeNode(int val) { this.val = val; }
9. *     TreeNode(int val, TreeNode left, TreeNode right) {
10. *         this.val = val;
11. *         this.left = left;
12. *         this.right = right;
13. *     }
14. * }
15. */
16. class Solution {
18.     // 存储每层的节点值
19.     List<List<Integer>> levels = new ArrayList<>();
21.     // 主方法：返回二叉树的层序遍历结果
22.     public List<List<Integer>> levelOrder(TreeNode root) {
23.         // 如果根节点为空，直接返回 levels（会是空列表）
24.         if (root == null) {
25.             return levels;
26.         }
27.         // 调用辅助方法进行层序遍历
28.         helper(root, 0);
29.         // 返回层序遍历结果
30.         return levels;
31.     }
33.     // 递归辅助方法进行层序遍历
34.     public void helper(TreeNode root, Integer level) {
35.         // 如果当前层级与 levels 的大小一致，表示需要新建一个列表来存储当前层的节点
36.         if (levels.size() == level) {
37.             levels.add(new ArrayList<>()); // 新建一个空的子列表
38.         }
39.         // 将当前节点的值加入对应层的列表中
40.         levels.get(level).add(root.val);
42.         // 如果当前节点有左子节点，递归处理左子树，层级 +1
43.         if (root.left != null) {
44.             helper(root.left, level + 1);
45.         }
46.         // 如果当前节点有右子节点，递归处理右子树，层级 +1
47.         if (root.right != null) {
48.             helper(root.right, level + 1);
49.         }
50.     }
52. }

复制代码

103. 二叉树的锯齿形层序遍历

1. /**
2. * Definition for a binary tree node.
3. * public class TreeNode {
4. *     int val;
5. *     TreeNode left;
6. *     TreeNode right;
7. *     TreeNode() {}
8. *     TreeNode(int val) { this.val = val; }
9. *     TreeNode(int val, TreeNode left, TreeNode right) {
10. *         this.val = val;
11. *         this.left = left;
12. *         this.right = right;
13. *     }
14. * }
15. */
16. class Solution {
17.     public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
18.         List<List<Integer>> ans = new ArrayList<>(); // 用于存放最终结果
19.         if (root == null) { // 如果根节点为空，返回空的结果
20.             return ans;
21.         }
23.         Queue<TreeNode> nodeQueue = new ArrayDeque<>(); // 初始化队列以进行层次遍历
24.         nodeQueue.offer(root); // 将根节点加入队列
25.         boolean isLeftOrder = true; // 标志变量，指示当前层的遍历顺序
27.         // 当队列不为空时，进行遍历
28.         while (!nodeQueue.isEmpty()) {
29.             Deque<Integer> levelList = new LinkedList<>(); // 使用双端队列存储当前层的节点值
30.             int size = nodeQueue.size(); // 记录当前层的节点数量
32.             // 遍历当前层的所有节点
33.             for (int i = 0; i < size; i++) {
34.                 TreeNode curNode = nodeQueue.poll(); // 从队列中取出当前节点
36.                 // 根据当前层的遍历顺序，决定如何添加节点值
37.                 if (isLeftOrder) {
38.                     levelList.offerLast(curNode.val); // 从尾部添加节点值（左到右）
39.                 } else {
40.                     levelList.offerFirst(curNode.val); // 从头部添加节点值（右到左）
41.                 }
43.                 // 将当前节点的左子节点加入队列
44.                 if (curNode.left != null) {
45.                     nodeQueue.offer(curNode.left);
46.                 }
47.                 // 将当前节点的右子节点加入队列
48.                 if (curNode.right != null) {
49.                     nodeQueue.offer(curNode.right);
50.                 }
51.             }
53.             // 将当前层的值转换为列表并添加到结果集合中
54.             ans.add(new ArrayList<>(levelList));
55.             // 切换当前层的遍历顺序
56.             isLeftOrder = !isLeftOrder; // 反转顺序
57.         }
59.         return ans; // 返回包含锯齿形层次遍历的所有节点值的结果
60.     }
61. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。