# Populating Next Right Pointers in Each Node

> Given a binary tree
>
> ```
> struct TreeLinkNode {
>
>   TreeLinkNode \*left;
>
>   TreeLinkNode \*right;
>
>   TreeLinkNode \*next;
>
> }
> ```
>
> Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
>
> Initially, all next pointers are set to NULL.
>
> Note:
>
> You may only use constant extra space.
>
> You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

## Thoughts

对完美二叉树每个结点增加next指针指向每层下一个结点。不难想到按层遍历，对每个结点，假设它所在的层已经连好了，通过它去连接下一层的结点。利用完美二叉树的性质，让cur->right去连接cur->next->left实现跨子树连接。当前结点处理好后，直接利用它的next就蹦到本层下一个结点。当next为null时说明本层已经遍历完，下层都已连好，需要一个额外指针next\_lev记录下层第一个结点。

## Code

```cpp
/*
 * @lc app=leetcode id=116 lang=cpp
 *
 * [116] Populating Next Right Pointers in Each Node
 */

// @lc code=start
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() {}

    Node(int _val, Node* _left, Node* _right, Node* _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/
class Solution {
public:
    Node* connect(Node* root) {
        Node *cur = root, *next_lev = cur;
        while (cur != nullptr && cur->left != nullptr) {
            if (next_lev == cur) {
                next_lev = cur->left;
            }
            cur->left->next = cur->right;
            if (cur->next == nullptr) {
                cur = next_lev;
            } else {
                cur->right->next = cur->next->left;
                cur = cur->next;
            }
        }
        return root;
    }
};
// @lc code=end


```

## Analysis

Errors:

1. 初始化TreeLinkNode nextLevel = null错误; 导致只执行了第一层

时间复杂度O(n), 空间复杂度O(1).


---

# 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://hao-fu-1.gitbook.io/oj/binary_tree_and_divide_conquer/divide-and-concquer/populating-next-right-pointers-in-each-node.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.