题目

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

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

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

示例 1：
[中等] 116. 填充每个节点的下一个右侧节点指针 - 图1

输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。

示例 2：

输入：root = []
输出：[]

解答 & 代码

解法一：BFS 层序遍历

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        if(root == NULL)
            return root;

        queue<Node*> nodeQ;
        nodeQ.push(root);
        while(!nodeQ.empty())
        {
            int levelSize = nodeQ.size();
            for(int i = 0; i < levelSize; ++i)
            {
                Node* cur = nodeQ.front();
                nodeQ.pop();
                // 填充当前节点的 next 指针
                // - 如果当前节点不是这一层的最后一个节点，则将 next 指向其右侧节点
                // - 否则，当前节点是这一层的最后一个节点，next 设为 NULL
                cur->next = i == levelSize - 1 ? NULL : nodeQ.front();
                if(cur->left != NULL)
                    nodeQ.push(cur->left);
                if(cur->right != NULL)
                    nodeQ.push(cur->right);
            }
        }
        return root;
    }
};

复杂度分析：设二叉树共 N 个节点

时间复杂度 O(N)：遍历每个节点一次
空间复杂度 O(N)：队列 nodeQ 中存储的节点个数不会超过 N

执行结果：

执行结果：通过

执行用时：28 ms, 在所有 C++ 提交中击败了 6.31% 的用户
内存消耗：16.6 MB, 在所有 C++ 提交中击败了 44.29% 的用户

解法二：DFS

题目要将每层的节点都串成一个链表。

如何将题目的要求细化成每个节点需要做的事情？

如果 DFS 函数只传入一个节点 **root**，我们只能让它的左子节点指向右子节点，但不能让 root 的右子节点指向 root 的兄弟节点的左子节点。也就是说，无法连接不同父节点的两个相邻节点。
解决办法：DFS 函数传入两个相邻节点
题目的要求就细化成了：将每两个相邻节点都连接起来 ```cpp / // Definition for a Node. class Node { public: int val; Node left; Node right; Node next;

Node() : val(0), left(NULL), right(NULL), next(NULL) {}

Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

Node(int _val, Node _left, Node _right, Node* _next)
```
  : val(_val), left(_left), right(_right), next(_next) {}
```
}; */

class Solution { private: // DFS，传入两个相邻节点 root1 和 root2，递归将这两棵树的相邻节点都连接起来 void connectTwoNode(Node root1, Node root2) { // 递归结束条件：有一个节点为 NULL，说明当前已在最后一层（完美二叉树），不用再往下层递归 if(root1 == NULL || root2 == NULL) return;

    // 前序位置：连接传入的两个节点
    root1->next = root2;
    // 递归
    // 连接相同父节点的两个相邻节点
    connectTwoNode(root1->left, root1->right);
    connectTwoNode(root2->left, root2->right);
    // 连接不同父节点的两个相邻节点
    connectTwoNode(root1->right, root2->left);
}

public: Node connect(Node root) { if(root == NULL) return root; connectTwoNode(root->left, root->right); return root; } };

复杂度分析：设二叉树共 N 个节点

- 时间复杂度 O(N)：遍历每个节点一次
- 空间复杂度 O(log N)：栈空间取决于递归深度，即二叉树的高度

执行结果：

执行结果：通过

执行用时：20 ms, 在所有 C++ 提交中击败了 54.53% 的用户内存消耗：16.4 MB, 在所有 C++ 提交中击败了 77.31% 的用户 ```