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

男娘i 2022-09-14 09:43 117阅读 0赞

注：和116题的差别在于，上一题的条件是满二叉树，而此题是二叉树，解题思路一样，无变化。

题目链接：[https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii/][https_leetcode-cn.com_problems_populating-next-right-pointers-in-each-node-ii]  
题目如下：  
![在这里插入图片描述][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) {
        
            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();
    
                    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 root;
        }
    };

[https_leetcode-cn.com_problems_populating-next-right-pointers-in-each-node-ii]: https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/532c0e4c79f444ecb5168ce97b3a40b7.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/50a8b5d466ba45159e672e73b694346c.png