题目描述（中等难度）

给定一个满二叉树，每个节点多了一个指针，然后将所有的next指针指向它的右边的节点。并且要求空间复杂度是O(1)。

解法一 BFS

如果没有要求空间复杂度这道题就简单多了，我们只需要用一个队列做BFS，BFS参见。然后按顺序将每个节点连起来就可以了。

当然既然题目要求了空间复杂度，那么我们来考虑下不用队列该怎么处理。只需要解决三个问题就够了。

三个问题都解决了，就可以写代码了。利用三个指针，start 指向每层的开始节点，cur指向当前遍历的节点，pre指向当前遍历的节点的前一个节点。

如上图，我们需要把 pre 的左孩子的 next 指向右孩子，pre 的右孩子的next指向的左孩子。

分享下 leetcode 的高票回答的代码，看起来更简洁一些，C++ 写的。

我的代码里的变量和他的变量对应关系如下。

除了变量名不一样，算法本质还是一样的。

题目让我们初始化 next 指针，初始化过程中我们又利用到了指针，很巧妙了。

添加好友一起进步~

如果觉得有帮助的话，可以点击这里给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击查看详情