# 117. 填充每个节点的下一个右侧节点指针 II

<https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii/>

## 解法一：层序

和116题一样的代码

```python
class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return root
        queue = [root]
        while queue:
            last = None     #记录同一层前一个结点，初始为空
            for _ in range(len(queue)):
                node = queue.pop(0)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
                if last:
                    last.next = node
                last = node
        return root
```

## 解法二：递归

注意不能前序，应该先递归处理右子树再左。因为每次处理root时得用到root.next的信息，所以必须先对右侧处理。

```python
class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return root
        #若有左子，且有右子，则左子连接右子
      	#无右子，则左子连接父亲右侧的左（或右）子
        if root.left:
            if root.right:
                root.left.next = root.right
            else:
                next = root.next
                while next:
                    if next.left:
                        root.left.next = next.left
                        break
                    if next.right:
                        root.left.next = next.right
                        break
                    next = next.next    #无子则进入下一个
        #若有右子，连接父亲右侧的左（或右）子
        if root.right:
            next = root.next
            while next:
                if next.left:
                    root.right.next = next.left
                    break
                if next.right:
                    root.right.next = next.right
                    break
                next = next.next
        #先递归右子树，再递归左子树   
        root.right = self.connect(root.right)
        root.left = self.connect(root.left)
        return root
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://cai-sen-se.gitbook.io/leetcode/1-200/117.-tian-chong-mei-ge-jie-dian-de-xia-yi-ge-you-ce-jie-dian-zhi-zhen-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.