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