
<p align="center">
  <a href="https://mp.weixin.qq.com/s/RsdcQ9umo09R6cfnwXZlrQ"><img src="https://img.shields.io/badge/PDF下载-代码随想录-blueviolet" alt=""></a>
  <a href="https://mp.weixin.qq.com/s/b66DFkOp8OOxdZC_xLZxfw"><img src="https://img.shields.io/badge/刷题-微信群-green" alt=""></a>
  <a href="https://space.bilibili.com/525438321"><img src="https://img.shields.io/badge/B站-代码随想录-orange" alt=""></a>
  <a href="https://mp.weixin.qq.com/s/QVF6upVMSbgvZy8lHZS3CQ"><img src="https://img.shields.io/badge/知识星球-代码随想录-blue" alt=""></a>
</p>
<p align="center"><strong>欢迎大家<a href="https://mp.weixin.qq.com/s/tqCxrMEU-ajQumL1i8im9A">参与本项目</a>，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！</strong></p>

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

链接：https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

```
struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}
```

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

进阶：
* 你只能使用常量级额外空间。
* 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

![](https://code-thinking-1253855093.file.myqcloud.com/pics/20210727143202.png)

# 思路

注意题目提示内容，：
* 你只能使用常量级额外空间。
* 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

基本上就是要求使用递归了，迭代的方式一定会用到栈或者队列。

## 递归

一想用递归怎么做呢，虽然层序遍历是最直观的，但是递归的方式确实不好想。

如图，假如当前操作的节点是cur：

<img src='https://code-thinking.cdn.bcebos.com/pics/116.填充每个节点的下一个右侧节点指针1.png' width=600> </img></div>

最关键的点是可以通过上一层递归 搭出来的线，进行本次搭线。

图中cur节点为元素4，那么搭线的逻辑代码：（**注意注释中操作1和操作2和图中的对应关系**）

```C++
if (cur->left) cur->left->next = cur->right; // 操作1
if (cur->right) {
    if (cur->next) cur->right->next = cur->next->left; // 操作2
    else cur->right->next = NULL;
}
```

理解到这里，使用前序遍历，那么不难写出如下代码：


```C++
class Solution {
private:
    void traversal(Node* cur) {
        if (cur == NULL) return;
                                // 中
        if (cur->left) cur->left->next = cur->right; // 操作1
        if (cur->right) {
            if (cur->next) cur->right->next = cur->next->left; // 操作2
            else cur->right->next = NULL;
        }
        traversal(cur->left);   // 左
        traversal(cur->right);  // 右
    }
public:
    Node* connect(Node* root) {
        traversal(root);
        return root;
    }
};
```

## 迭代（层序遍历）

本题使用层序遍历是最为直观的，如果对层序遍历不了解，看这篇：[二叉树：层序遍历登场！](https://mp.weixin.qq.com/s/4-bDKi7SdwfBGRm9FYduiA)。

层序遍历本来就是一层一层的去遍历，记录一层的头结点（nodePre），然后让nodePre指向当前遍历的节点就可以了。

代码如下：

```C++
class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> que;
        if (root != NULL) que.push(root);
        while (!que.empty()) {
            int size = que.size();
            vector<int> vec;
            Node* nodePre;
            Node* node;
            for (int i = 0; i < size; i++) { // 开始每一层的遍历
                if (i == 0) {
                    nodePre = que.front(); // 记录一层的头结点
                    que.pop();
                    node = nodePre;
                } else {
                    node = que.front();
                    que.pop();
                    nodePre->next = node; // 本层前一个节点next指向本节点
                    nodePre = nodePre->next;
                }
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            nodePre->next = NULL; // 本层最后一个节点指向NULL
        }
        return root;
    }
};
```

# 其他语言版本

## Java

```java

```

## Python

```python

```

## Go

```go

```

## JavaScript

```js
const connect = root => {
    if (!root) return root;
    // 根节点入队
    const Q = [root];
    while (Q.length) {
        const len = Q.length;
        // 遍历这一层的所有节点
        for (let i = 0; i < len; i++) {
            // 队头出队
            const node = Q.shift();
            // 连接
            if (i < len - 1) {
                // 新的队头是node的右边元素
                node.next = Q[0];
            }
            // 队头左节点有值，放入队列
            node.left && Q.push(node.left);
            // 队头右节点有值，放入队列
            node.right && Q.push(node.right);
        }
    }
    return root;
};
```

-----------------------
* 作者微信：[程序员Carl](https://mp.weixin.qq.com/s/b66DFkOp8OOxdZC_xLZxfw)
* B站视频：[代码随想录](https://space.bilibili.com/525438321)
* 知识星球：[代码随想录](https://mp.weixin.qq.com/s/QVF6upVMSbgvZy8lHZS3CQ)
<div align="center"><img src=../pics/公众号.png width=450 alt=> </img></div>

