时间戳

首页 > 解决方案 > 二叉树级序遍历调试

java - 二叉树级序遍历调试

问题描述

我有这个二叉树

    3
   / \
  9  20
    /  \
   15   7

我想以这种格式打印它的级别顺序遍历

[
  [3],
  [9,20],
  [15,7]
]

所以我使用一个队列和两个列表编写了这段代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue=new LinkedList<TreeNode>();
        List<Integer> list=new ArrayList<>();
        List<List<Integer>> res=new LinkedList<>();
        if(root!=null)
        {
            queue.add(root);
        }

        while(!queue.isEmpty())
        {
            int size=queue.size();
            for(int i=0;i<size;i++)
            {

            TreeNode tempNode=queue.poll();
            list.add(tempNode.val);
            if(tempNode.left!=null)
                queue.add(tempNode.left);
            if(tempNode.right!=null)
                queue.add(tempNode.right);
            }
            res.add(list);
            list.clear();

        }

        return res;

    }
}

但是当我检查输出时它返回

[[],[],[]]

我已经花了 1 个多小时来调试问题，并且我确信我的代码是正确的（这不是！）我不知道在向其添加数据后清除 res 列表的内容是什么。请帮我修复错误。

我相信 list.clear() 也会清除 res 中添加的列表项。

就是这样，那么假设

x=34;
list.add(x);
x=45;
System.out.println(list); // it will still print [34]

但是使用列表列表并在向其中添加项目之后，如果您修改内部列表..它也会修改您的列表列表。为什么 ？

int x=3;
li.add(x);
x=45;
res.add(li);
System.out.println(li);
li.remove(0);
li.add(23);
System.out.println(res);

标签： javadata-structuresbinary-tree

解决方案

发生这种情况是因为您正在操作一个对象，它不会发生在原始类型上

您正在使用单个list实例，在外部列表中添加列表后，您仍在操作同一个实例，您总是引用同一个 List实例

您在外部列表中多次添加并清除它，您需要在每次迭代时创建新实例：

while(!queue.isEmpty()){
    int size = queue.size();
    for(int i=0 ; i<size;i++){
        TreeNode tempNode = queue.poll();
        list.add(tempNode.val);
        if(tempNode.left!=null)
            queue.add(tempNode.left);
        if(tempNode.right!=null)
            queue.add(tempNode.right);
    }
    res.add(list);
    list = new ArrayList<>();
}

推荐阅读