Leetcode BFS 问题：为什么我的队列中有一个空值？

Question

我正在做一个 leetcode BFS 问题：https://leetcode.com/problems/populating-next-right-pointers-in-each-node/description/

我的解决方案如下，通过：

class Solution {
    public Node connect(Node root) {
        Queue<Node> q = new LinkedList<>();
        q.add(root);
      
        while(!q.isEmpty())
        {
            Queue<Node> childQ = new LinkedList<>();
            while(!q.isEmpty())
            {
                Node curr=q.remove();
                if(curr==null) break;
                curr.next=q.peek();
                if(curr.left!=null)
                {childQ.add(curr.left);childQ.add(curr.right);}
            }
            q=childQ;
        }
        return root;
    }
}

只有在我为队列中的最后一个节点添加空检查后它才会通过。

if(curr==null) break;

但是为什么 curr 会是 null？在最后一次迭代中，某处将 null 传递给 childQ。但我无法发现在哪里。有人可以借给我一只眼睛吗？

谢谢！

Answer 1

null

不是来自

childQ

队列。它只会在

root

是

null

时发生，因为代码挑战描述说树中的节点数可能为 0。这意味着

root

是

null

.

所以你 can 删除那个

if

语句，但是你应该在函数的最开始有一个来检测这个极端情况：

    public Node connect(Node root) {
        if(root==null) return root; // corner case
        Queue<Node> q = new LinkedList<>();
        q.add(root);
      
        while(!q.isEmpty())
        {
            Queue<Node> childQ = new LinkedList<>();
            while(!q.isEmpty())
            {
                Node curr=q.remove();
                curr.next=q.peek();
                if(curr.left!=null)
                {
                    childQ.add(curr.left);
                    childQ.add(curr.right);
                }
            }
            q=childQ;
        }
        return root;
    }