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 题的递归解法（适用于普通二叉树）

由于树的结构不确定，我们需要：

1. 找到当前节点的 next 节点的第一个有效子节点（可能是 next.left 或 next.right）。

2. 递归处理右子树，再处理左子树（因为 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;}
};