# 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).