LeetCode117_填充每个结点的下一个右侧结点指针Ⅱ

标签：#树 #深度优先遍历 #广度优先遍历 #链表 #二叉树

Ⅰ. 题目

• 给定一个二叉树：

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

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

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

Ⅱ. 示例

· 示例 1：
输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]
解释：序列化输出按层序遍历顺序（由 next 指针连接），‘#’ 表示每层的末尾。

· 示例 2：
输入：root = []
输出：[]

0. 个人方法

由题目可知，本题是要解决一个层序遍历（BFS）的问题。因此，可以通过队列“先进先出”的性质，将树按层连接起来。

1. 使用队列 std::queue<Node*> q 来存储每层的节点；
2. 每次处理一层中的所有节点，并将下一层的子节点加入队列；
3. 对于同一层的节点，设置 next 指针为右边相邻的节点；
4. 最后，当queue为空时，完成遍历。

/*
// 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) {std::queue<Node*> q;if (root != nullptr){q.push(root);}while (!q.empty()){int levelSize = q.size();for (int i=0; i<levelSize; i++){Node* current = q.front();q.pop();if (i < levelSize-1){current->next = q.front();}if (current->left)q.push(current->left);if (current->right)q.push(current->right);}}return root;}
};

• 复杂度分析（记树上的点的个数为 N）

  • 时间复杂度：O(N)。我们需要遍历这棵树上所有的点，时间复杂度为 O(N)。

  • 空间复杂度：O(N)。即队列的空间代价。