116. 填充每个节点的下一个右侧节点指针

type

Post

status

Published

slug

2023/04/02/leetcode-116. 填充每个节点的下一个右侧节点指针

summary

116. 填充每个节点的下一个右侧节点指针

题目描述

解题思路

函数connect以指向二叉树根节点的Node指针root作为输入。

用根节点初始化队列queue。两个变量flag和i分别初始化为1和0。变量flag跟踪当前层中的节点数，i跟踪当前层中已处理的节点数。

while循环运行直到队列为空。

在while循环内，队列的前端节点被移除并存储在临时指针tmp中。如果i大于或等于flag，则表示当前层中的所有节点已处理完毕。因此，tmp连接到NULL，并将i和flag重置为0和flag乘以2。

否则，tmp连接到队列的前端节点。

如果tmp同时具有左右子节点，则将它们添加到队列中。

函数返回根节点。

解题代码


#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <stack>
#include <queue>

using namespace std;

// 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 *> queue;
        queue.push(root);
        int flag = 1;
        int i = 0;
        while(!queue.empty()){
            i++;
            Node *tmp = queue.front();
            queue.pop();
            if(i >= flag){
                tmp->next = NULL;
                i =0;
                flag *= 2;
            } else {
                tmp->next = queue.front();
            }
            if (tmp->left && tmp->right){
                queue.push(tmp->left);
                queue.push(tmp->right);
            }
        }
        return root;
    }
};


int main(){
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);
    root->right->right = new Node(7);

    Solution solution;
    solution.connect(root);
    // 116. 填充每个节点的下一个右侧节点指针
    for (int i = 0; i < 7; ++i) {
        Node *tmp = root;
        while(tmp){
            cout << tmp->val << " ";
            tmp = tmp->next;
        }
        cout << endl;
        root = root->left;
    }

    return 0;
}