力扣-116题填充每个节点的下一个右侧节点指针（C++）- 层次遍历

冷不防 2022-09-14 09:42 102阅读 0赞

题目链接：[https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/][https_leetcode-cn.com_problems_populating-next-right-pointers-in-each-node]  
题目如下：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16 1]

/*
    // 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) {
        
            Node* node=root;
            queue<Node*> que;
    
            if(root==NULL) return root;
            que.push(root);
    
            while(!que.empty()){
        
                int size=que.size();
    
                while(size--){
        
                    Node* tmp=que.front();
                    que.pop();
    
                    //当到达最后一个节点，填充NULL，否则，指向下一个节点
                    if(size!=0) tmp->next=que.front();
                    else tmp->next=NULL;
    
                    if(tmp->left) que.push(tmp->left);
                    if(tmp->right) que.push(tmp->right);
                }
            }
    
            return node;
        }
    };

[https_leetcode-cn.com_problems_populating-next-right-pointers-in-each-node]: https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/83fdbbcaf300476f8fefd8e4978e24fd.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/6ffab4a44e804e43bee0fdb51b390157.png