题目描述

给定一棵二叉树：

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

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

注意：

• 只能使用额外的 $O(1)$ 空间；
• 可以使用递归算法，即可以不考虑系统栈所用的空间；

样例

给定如下完美二叉树

     1
   /  \
  2    3
 / \    \
4   5    7

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

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

算法

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

这道题目和 Populating Next Right Pointers in Each Node 类似，不同点在于这道题目的输入数据不一定是一棵完美二叉树。

从根节点开始宽度优先遍历，每次遍历一层，从左到右依次遍历每个节点。
遍历时维护下一层节点的链表。对于每个节点，依次判断它的左儿子和右儿子是否在存在，如果存在，则插入下一层链表的末尾。

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

• 第一步，遍历根节点，依次将它的左右儿子插入下一层链表，得到 2->3；
• 第二步，从左到右遍历第二层，即遍历 2->3，依次将它们的子节点插入下一层链表，得到 4->5->7；
• 第三步，遍历到叶节点层，算法结束；

时间复杂度分析：每个节点仅会遍历一次。对于每个节点，遍历时维护下一层链表的时间复杂度是 $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:
    Node* connect(Node *root) {
        auto head = root;
        while (root)
        {
            Node *dummy = new Node(0);
            Node *tail = dummy;
            while (root)
            {
                if (root->left)
                {
                    tail->next = root->left;
                    tail = tail->next;
                }
                if (root->right)
                {
                    tail->next = root->right;
                    tail = tail->next;
                }
                root = root->next;
            }
            root = dummy->next;
        }
        return head;
    }
};