欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

(128)116. 填充每个节点的下一个右侧节点指针(leetcode)

程序员文章站 2022-05-20 16:14:23
...
题目链接:
https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/
难度:中等
116. 填充每个节点的下一个右侧节点指针
	给定一个完美二叉树,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:
	struct Node {
	  int val;
	  Node *left;
	  Node *right;
	  Node *next;
	}
	填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。
	初始状态下,所有 next 指针都被设置为 NULL。
提示:
	你只能使用常量级额外空间。
	使用递归解题也符合要求,本题中递归程序占用的栈空间不算做额外的空间复杂度。

有点简单。。。一次过(好吧 其实是两次 第一次提交的时候忘记root==nullptr了) 话说这题前几天不是才做了吗,不对,比之前还要简单。。。。
使用队列就可以了

/*
// 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) {
        if(root==nullptr){
            return root;
        }
        queue<Node*> que;
        que.push(root);
        while(!que.empty()){
            int n=que.size();
            Node* pre=nullptr;
            for(int i=0;i<n;++i){
                auto t=que.front();
                que.pop();
                if(pre!=nullptr){
                    pre->next=t;
                }
                pre=t;
                if(t->left!=nullptr){
                    que.push(t->left);
                    que.push(t->right);
                }
            }
        }
        return root;
    }
};

在第 n 层为第 n+1 层进行赋值

class Solution {
public:
    Node* connect(Node* root) {
        if(root==nullptr){
            return root;
        }
        auto head=root;
        while(head->left!=nullptr){
            auto cur=head;
            while(cur!=nullptr){
                cur->left->next=cur->right;
                if(cur->next!=nullptr){
                    cur->right->next=cur->next->left;
                }
                cur=cur->next;
            }
            head=head->left;
        }
        return root;
    }
};