leetcode117 填充每个节点的下一个右侧节点指针2
LeetCode 116 和 117 都是关于填充二叉树节点的 next 指针的问题，但它们的区别在于 树的类型 不同，117与 116 题类似，但给定的树是 普通二叉树（不一定完全填充），即某些节点可能缺少左或右子节点。
-
树的结构 不保证是完美的，可能缺失某些子节点。
-
因此，116 题的简单递归方法 不能直接适用，需要更通用的解法（如 BFS + 链表连接 或 逐层处理）。
-
需要额外处理 子节点缺失 的情况，导致代码比 116 题复杂。
116 题的 BFS（层级遍历） 解法可以直接用于 117 题，因为 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) {queue<Node*> q;if(root == NULL) return root;Node* node;Node* prenode;q.push(root);while(!q.empty()){int size = q.size();for(int i = 0; i < size; i++){if(i == 0){prenode = q.front();q.pop();node = prenode;}else{node = q.front();q.pop();prenode->next = node;prenode = prenode->next;}if (node->left) q.push(node->left);if (node->right) q.push(node->right);}node->next = NULL;}return root;}
};递归：
116 题的递归解法利用了 完美二叉树的对称性：
117 题的树可能 缺少左或右子节点，比如：
-
root.left存在，但root.right不存在，此时root.left.next不能直接指向root.right（因为root.right是None）。 -
root.next的子节点可能不存在，导致root.right.next = root.next.left失效。
117 题的递归解法（适用于普通二叉树）
由于树的结构不确定，我们需要：
-
找到当前节点的
next节点的第一个有效子节点（可能是next.left或next.right）。 -
递归处理右子树，再处理左子树（因为
next链是从左到右建立的，必须先确保右侧的next关系已经建立）。
class Solution {
public:Node* connect(Node* root) {if (!root) return nullptr;Node* curr = root; // 当前层的头节点Node dummy(0); // 虚拟头节点，用于连接下一层Node* prev = &dummy; // 用于遍历下一层while (curr) {// 遍历当前层，连接下一层if (curr->left) {prev->next = curr->left;prev = prev->next;}if (curr->right) {prev->next = curr->right;prev = prev->next;}curr = curr->next; // 移动到当前层的下一个节点// 如果当前层遍历完毕，进入下一层if (!curr) {curr = dummy.next;dummy.next = nullptr;prev = &dummy;}}return root;}
};