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;}
};