问答

当前位置
  • 首页
  • 问答
  • 填充每个结点的右结点指针II · Populating Next Right Pointers in Each Node II

填充每个结点的右结点指针II · Populating Next Right Pointers in Each Node II

  • Ta: 杜承澔

请问助教老师:
我想用bfs做这个题目https://www.jiuzhang.com/solution/populating-next-right-pointers-in-each-node-ii/#tag-highlight-lang-python
想用一个队列的方法,类似于level order traversal的答案https://www.jiuzhang.com/solution/binary-tree-level-order-traversal/#tag-highlight-lang-python 用for loop控制node都是当前层的。如图
图片
但是这样似乎是错的。请老师帮忙讲解一下。请问output里的$ref什么意思呀?另外能不能顺便告知如果可以用一个队列来做的话,应该怎么改这个code呢?谢谢
(lintcode看不到题目了,不好意思)

1 个回复

2019-09-11 carry

right":{"$ref":"4"}表示右节点指向id为4的节点。

出错是因为在for循环中,每一次迭代queue的length都可能会变换,所以在for循环之前,应该记录下queue的length的值。
```python
class Solution:
def connect(self, root: 'Node') -> 'Node':
if root is None:
return root

    queue = collections.deque([root])
    while queue:
        size = len(queue)
        for i in range(size):
            node = queue.popleft()
            if i < size - 1:
                node.next = queue[0]
            else:
                node.next = None
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return root

我来回答

您没有权限

为提高问答质量,问答版块发言权限只向九章学员开放

登录 注册

© Jiu Zhang 2013-. All rights reserved. 京ICP备16004690号-1