java - 使用两个队列的级别顺序遍历二叉树
问题描述
Leetcode 问题:https ://leetcode.com/problems/binary-tree-level-order-traversal/
我有两个队列,我清空我的第一个队列 (q),同时将元素添加到我的第二个队列 (q2),这样我可以获得级别。当第一个队列为空时,我将它传递给函数以创建该级别的 ArrayList 并添加到我的结果值,如果 q2 为空,则意味着没有添加任何内容,因此我们可以跳出循环并返回函数. 我必须手动添加第一个节点。问题是只添加了中间级别,而不是其余的。
/**
* 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>> levelOrder(TreeNode root) {
if(root == null) {
return null;
}
List<List<Integer>> returnList = new ArrayList<>();
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
List<Integer> tempList = new ArrayList<>();
tempList.add(root.val);
returnList.add(tempList);
while(true) {
Queue<TreeNode> q2 = new LinkedList<>();
while(!q.isEmpty()) {
TreeNode node = q.remove();
if(node.left != null) {
q2.add(node.left);
}
if(node.right != null) {
q2.add(node.right);
}
}
if(q2.isEmpty()) {
break;
}
q = q2;
addList(returnList, q2);
}
return returnList;
}
public static void addList(List<List<Integer>> returnList, Queue<TreeNode> q2) {
List<Integer> tempList = new ArrayList<>();
int size = q2.size();
for(int i = 0; i < size; i++) {
int val = q2.remove().val;
System.out.println(val);
tempList.add(val);
}
returnList.add(tempList);
}
}
解决方案
问题与这部分代码有关:
q = q2;
addList(returnList, q2);
该函数addList
将清空给定的队列q2
,并对其进行调用remove
。由于q
已成为对同一队列的引用,因此您已清空q
,因此外循环的下一次迭代将不会进入内循环,并使用 退出外循环break
。
为避免这种情况发生,请确保remove
调用未在 : 上执行q
:制作副本:
q = new LinkedList<>(q2);
addList(returnList, q2);
或者,或者:
q = q2;
addList(returnList, new LinkedList<>(q2));
推荐阅读
- docker - 如何在 Docker 映像中保留 Jetbrains Teamcity 服务器实例的状态,以便在没有我的本地目录卷的情况下部署到其他人
- c# - 如何在事件处理程序中调用 android 特定代码
- powershell - 如何使用 PowerShell 处理 GUI 按钮以执行带参数的函数?
- math - 如何为以下匹配问题编写最有效的代码?
- excel - 如果有任何失败,如何显示所有失败,如果没有,则显示没有失败框
- reactjs - React/React Hooks:输入时出现未知的道具类型错误,无法弄清楚如何解决
- python - 如何在给定时间记录和保存用户可编辑的 Django 模型实例
- javascript - 将 HTML 输出解析为本地文件?
- reactjs - How to fix my useEffect or firestore functions to render the profile in the table
- google-analytics - 为什么推迟开始日期会导致 Google Analytics(分析)报告查询返回 0 个结果?