LeetCode之二叉树层次遍历 - ToB企服应用市场:ToB评测及商务社交产业平台

/**
* 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;
}
// 进行层序遍历，填充 levels
helper(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);
// 如果当前节点有左子树，继续递归到左子树，层级 +1
if (root.left != null) {
helper(root.left, level + 1);
}
// 如果当前节点有右子树，继续递归到右子树，层级 +1
if (root.right != null) {
helper(root.right, level + 1);
}
}
}

复制代码

/**
* 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);
}
}

复制代码

/**
* 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);
// 如果当前节点有左子节点，递归处理左子树，层级 +1
if (root.left != null) {
helper(root.left, level + 1);
}
// 如果当前节点有右子节点，递归处理右子树，层级 +1
if (root.right != null) {
helper(root.right, level + 1);
}
}
}

复制代码

/**
* 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; // 返回包含锯齿形层次遍历的所有节点值的结果
}
}

复制代码