> For the complete documentation index, see [llms.txt](https://r24zeng.gitbook.io/leetcode-notebook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://r24zeng.gitbook.io/leetcode-notebook/bu-chong-2140-dao/116.-populating-next-right-pointers-in-each-node.md).

# 116. Populating Next Right Pointers in Each Node

\# Medium

{% hint style="info" %}
Two methods:

1. Recursive (由于是完全二叉树，所以若节点的左子结点存在的话，其右子节点必定存在，所以左子结点的 next 指针可以直接指向其右子节点，对于其右子节点的处理方法是，判断其父节点的 next 是否为空，若不为空，则指向其 next 指针指向的节点的左子结点，若为空则指向 NULL)
2. No-recursive + BFS(use queue)
   {% endhint %}

{% tabs %}
{% tab title="Python (2)" %}

```python
# 方法二，非递归
# 我写的
"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        # edge case
        if root == None:
            return None
        
        # regular case
        queue = []
        queue.append(root)
        while len(queue) != 0:
            n = len(queue)
            tmp = queue.pop(0)
            while n >= 1:
                if tmp.left != None:
                    queue.append(tmp.left)
                    queue.append(tmp.right)
                    
                if n == 1:
                    tmp.next = None
                else:
                    right = queue.pop(0)
                    tmp.next = right
                    tmp = right
                n -= 1
                
        return root
```

{% endtab %}

{% tab title="C++ (1)" %}

```cpp
// 方法一，递归的方法，找父节点？
// 不需要，只判断父节点，通过父节点给子节点加上next
// 不是我写的
class Solution {
public:
    Node* connect(Node* root) {
        if (!root) return NULL;
        if (root->left) root->left->next = root->right;
        if (root->right) root->right->next = root->next? root->next->left : NULL;
        connect(root->left);
        connect(root->right);
        return root;
    }
};
```

{% endtab %}
{% endtabs %}

非递归的方法，n 为tree的高度，时间复杂度为 $$O(2^n - 1)$$ ，因为需要遍历所有的节点，空间复杂度为叶子节点的个数 $$O(2^{n-1})$$