[数据结构与算法]LeetCode_116 填充每个节点的下一个右侧节点指针

1、题目：填充每个节点的下一个右侧节点指针

给定一个?完美二叉树?，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
? int val;
? Node *left;
? Node *right;
? Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

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

2、解题思路

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。即在每一层中，对所有元素进行操作，所以我们在层序遍历的基础上进行操作。

LeetCode_102 二叉树的层序遍历_W__winter的博客-CSDN博客

3、代码

class Solution 
{
public:
    Node* connect(Node* root) 
    {
        queue<Node*> que;
        if (root != NULL) 
            que.push(root);
        
        while (!que.empty()) 
        {
            int size = que.size();
            
            // 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
            for (int i = 0; i < size; i++) 
            {
                Node* node = que.front();
                que.pop();
                if (i == size - 1)
                    node->next = NULL;
                else 
                    node->next = que.front();                
                if (node->left) 
                    que.push(node->left);
                if (node->right) 
                    que.push(node->right);
            }
            
        }
        return root;
    }
};