题目描述

给定一棵二叉树：

struct TreeLinkNode {
  TreeLinkNode *left;
  TreeLinkNode *right;
  TreeLinkNode *next;
}

将所有next指针指向它的右边相邻的节点。如果右边没有节点，则置为NULL。
初始时所有next指针均指向 NULL。

注意：

• 只能使用额外的 $O(1)$ 空间；
• 可以使用递归算法，即可以不考虑系统栈所用的空间；
• 给定的是一棵完美二叉树，即所有叶子节点在同一层，且所有内部节点都有两个儿子；

样例

给定如下完美二叉树

     1
   /  \
  2    3
 / \  / \
4  5  6  7

运行完你的函数后，应该得到如下结果：

     1 -> NULL
   /  \
  2 -> 3 -> NULL
 / \  / \
4->5->6->7 -> NULL

算法

(BFS，树的遍历) $O(n)$

从根节点开始宽度优先遍历，每次遍历一层，遍历时按从左到右的顺序，对于每个节点，先让左儿子指向右儿子，然后让右儿子指向下一个节点的左儿子。最后让这一层最右侧的节点指向NULL。
遍历到叶节点所在的层为止。

为了便于理解，我们模拟一下样例的操作流程：

• 第一步，遍历根节点，我们让根节点的左儿子指向右儿子，即让2指向3；
• 第二步，从左到右遍历第二层，先遍历2，让2的左儿子指向右儿子，即让4指向5，再让2的右儿子指向下一个节点的左儿子，即5指向6；然后遍历3，依次类推；
• 第三步，我们发现第三层已经是叶节点，算法终止；

时间复杂度分析：每个节点仅会遍历一次，遍历时修改指针的时间复杂度是 $O(1)$，所以总时间复杂度是 $O(n)$。

C++ 代码

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root)
    {
        if (!root) return;
        TreeLinkNode *last = root;
        while (last->left) // 直到遍历到叶节点
        {
            for (TreeLinkNode *p = last; p; p = p->next)
            {
                p->left->next = p->right;
                if (p->next) p->right->next = p->next->left;
                else p->right->next = 0;
            }
            last = last->left;
        }
    }
};