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

/*
// 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 q;
        if(root != NULL){
            q.push(root);
        }
        Node* temp = root;
        while(!q.empty()){
            int size = q.size();

            for(int i = 0; i < size; i++){
                root = q.front();
                q.pop();
                if(!q.empty())
                root->next = q.front(); 
                if(root->left)q.push(root->left);
                if(root->right)q.push(root->right);
            }
        }
        return temp;
    }
};

上边是个错误的解法,由于错误的案例好像有点似曾相识。

输入

[1,2,3,4,5,null,7]

输出

[1,#,2,3,4,5,7,#,4,5,7,#]

预期结果

[1,#,2,3,#,4,5,7,#]

果不其然,和上次一样的错法!!!

/*
// 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 q;
        if(root != NULL){
            q.push(root);
        }
        Node* temp = root;
        while(!q.empty()){
            int size = q.size();

            for(int i = 0; i < size; i++){
                root = q.front();
                q.pop();
                if(i != size - 1)root->next = q.front();
                //这里泥马的又一次利用了队列是否为空,来判断当前层是否遍历完成。
                //梅开二度,和上次一样的毛病
                if(root->left)q.push(root->left);
                if(root->right)q.push(root->right);
            }
        }
        return temp;
    }
};

                //这里泥马的又一次利用了队列是否为空,来判断当前层是否遍历完成。
                //梅开二度,和上次一样的毛病

上边这是用层序遍历的思路实现的

那么这个既然是一个个遍历的玩法,那么用指针也是可以做到的,他不就是一个骚气的链表么。

所以整体思路就是遍历,然后遍历要有核心,这里的核心就是从根节点开始,然后逐个搞,根节点遍历到倒数第二层的时候就结束了。因为这里遍历的是核心节点,操作的是他的儿子。

思路沿用之前的完美二叉树的思路,先把连接的情况分一下类:(这里有很重要的一点就是特殊和一般的关系,有时候针对一个一般的问题,直接去构思你可能没有什么思路,但是你利用一些特殊的情况去思考构思,可能就会有点门道了。最后你在把这个特殊情况的思路套在原来的一般的问题上,可能会有考虑不周的地方,但是经修改补足或许就可以了,起码是有个整体的方法框架了)。

可能当前的节点是有左右儿子的,也可能只有一个左或者右儿子,也可能是左右都没有。

那么对于第一种左右都有的,只需要把左儿子的next安排上就得了,然后呢?就需要找到下一个有儿子的节点或者走到空,该行结束了。

那么怎么实现上边的想法呢,首先判断连接容易,主要是后边的这个找到一个有儿子的或者找到最后的空。那么你找到了了有儿子的,然后呢?你需要把刚刚的右二子和你找到的这个连起来,那这里就需要两个指针了。第二根指针可以利用第一根指针进行初始化,也只需要在内部定义。

捋一下就是,利用指针一直往右走,直到空或者有儿子的节点。那么这种一直,,,直到,,,这种结构自然就想起来一个while循环了。while(temp->next->right/left != nullptr || temp->next ==NULL)  大概是这么个逻辑,直到遇上了,然后第一种空的情况直接切换到下一层了,这时候就需要一点准备了,第二种就是需要连接了。

当前是只有一个儿子的,那就还是一直往右走然后找到有儿子的或者找到空,就是相当于第一种情况连接之后的操作。

如果左右都没有的,那就找第一个有儿子的,找到之后更新root 下一轮迭代就行了。

/*
// 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* temp = root;
        Node* first = root;
        bool update = false;
        while(first != NULL && (first->left != NULL || first->right != NULL || first->next != NULL)){
            while(1){
                if(root->left != NULL && root->right != NULL){
                    if(update == false){
                        update = true;
                        first = root->left;
                    }
                    root->left->next = root->right;
                    Node* help = root;
                    while(help->next != NULL){
                        help = help->next;
                        if(help->left != NULL){
                            root->right->next = help->left;
                            root = help;
                            break; 
                        }
                        else if(help->right != NULL){
                            root->right->next = help->right;
                            root = help;
                            break;
                        }
                    }
                    if(help->next == NULL){
                        //走到头了
                        break;
                    }
                }
                else if(root->left != NULL && root->right == NULL){
                    if(update == false){
                        update = true;
                        first = root->left;
                    }
                    Node* help = root;
                    while(help->next != NULL){
                        help = help->next;
                        if(help->left != NULL){
                            root->left->next = help->left;
                            root = help;
                            break; 
                        }
                        else if(help->right != NULL){
                            root->left->next = help->right;
                            root = help;
                            break;
                        }
                    }
                    if(help->next == NULL){
                        //走到头了
                        break;
                    }
                }
                else if(root->left == NULL && root->left != NULL){
                    if(update == false){
                        update = true;
                        first = root->right;
                    }
                    Node* help = root;
                    while(help->next != NULL){
                        help = help->next;
                        if(help->left != NULL){
                            root->right->next = help->left;
                            root = help;
                            break; 
                        }
                        else if(help->right != NULL){
                            root->right->next = help->right;
                            root = help;
                            break;
                        }
                    }
                    if(help->next == NULL){
                        //走到头了
                        break;
                    }
                }
                else{//两个儿子都是空的
                    Node* help = root;
                    while(help->next != NULL){
                        help = help->next;
                        if(help->left != NULL || help->right != NULL){
                            root = help;
                            break;
                        }
                    }
                    if(help->next == NULL){
                        //说明到头了
                        break;
                    }
                }
            }
            //这一层结束了,需要更新点东西:
            if(update == false)return temp;
            update = false;
            root = first;
        }
        return temp;
    }
};
输入:
[3,9,20,null,null,15,7]
输出:
[3,#,9,20,#,15,#]
预期结果:
[3,#,9,20,#,15,7,#]

上边这个是错误的答案,在两个儿子都是空的情况下,他会一直向右走,走到空或者有儿子的节点,上边的思路后边紧跟着一行代码,if这时候root后边是空那么直接break了,那当前的这个root还没有连接呢!!前边也都有这个毛病。

/*
// 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* temp = root;
        Node* first = root;
        bool update = false;
        while(first != NULL && (first->left != NULL || first->right != NULL || first->next != NULL)){
            while(1){
                if(root->left != NULL && root->right != NULL){
                    if(update == false){
                        update = true;
                        first = root->left;
                    }
                    root->left->next = root->right;
                    Node* help = root;
                    while(help->next != NULL){
                        help = help->next;
                        if(help->left != NULL){
                            root->right->next = help->left;
                            root = help;
                            break; 
                        }
                        else if(help->right != NULL){
                            root->right->next = help->right;
                            root = help;
                            break;
                        }
                    }
                    if(root->left != NULL && root->right != NULL && root->left->next == root->right && help->next == NULL){
                        //走到头了
                        break;
                    }
                    if((root->left == NULL || root->right == NULL) && root->next == NULL){
                //上边的if只包含了两个儿子均不为空的情况要break,
                //并没有把只剩下单个儿子的情况给列出来,需要重新写一个
                        break;
                    }
                }
                else if(root->left != NULL && root->right == NULL){
                    if(update == false){
                        update = true;
                        first = root->left;
                    }
                    Node* help = root;
                    while(help->next != NULL){
                        help = help->next;
                        if(help->left != NULL){
                            root->left->next = help->left;
                            root = help;
                            break; 
                        }
                        else if(help->right != NULL){
                            root->left->next = help->right;
                            root = help;
                            break;
                        }
                    }
                    if(!(help->left != NULL&& help->right != NULL) && help->next == NULL){
                        //走到头了
                        break;
                    }
                }
                else if(root->left == NULL && root->right != NULL){
                    if(update == false){
                        update = true;
                        first = root->right;
                    }
                    Node* help = root;
                    while(help->next != NULL){
                        help = help->next;
                        if(help->left != NULL){
                            root->right->next = help->left;
                            root = help;
                            break; 
                        }
                        else if(help->right != NULL){
                            root->right->next = help->right;
                            root = help;
                            break;
                        }
                    }
                    if(!(help->left != NULL&& help->right != NULL) && help->next == NULL){
                        //走到头了
                        break;
                    }
                }
                else{//两个儿子都是空的
                    Node* help = root;
                    while(help->next != NULL){
                        help = help->next;
                        if(help->left != NULL || help->right != NULL){
                            root = help;
                            break;
                        }
                    }
                    if(!(help->left != NULL&& help->right != NULL) && help->next == NULL){
                        //说明到头了
                        //这里要对update更新!!!!!!!!!
                        if(help->right != NULL){
                            update = true;
                            first = root->right;
                        }
                        if(help->left != NULL){
                            update = true;
                            first = root->left;
                        }
                        break;
                    }
                }
            }
            //这一层结束了,需要更新点东西:
            if(update == false)return temp;
            update = false;
            root = first;
        }
        return temp;
    }
};

按照上边的指针遍历使用o(1)的空间,但是整体的思路过于繁杂。但是有一个点就是:

我对于这道题的提前构思花费了很多的时间,尽管他是很复杂的,但是我并没有去debug整太长时间,而且后来出错的时候也都是根据案例锁定位置,最后修修补补就解决了,所以说提前构思非常重要!!!!!!!

class Solution {
public:
    void handle(Node* &last, Node* &p, Node* &nextStart) {
        if (last) {
            last->next = p;
        } 
        if (!nextStart) {
            nextStart = p;
        }
        last = p;
    }

    Node* connect(Node* root) {
        if (!root) {
            return nullptr;
        }
        Node *start = root;
        while (start) {
            Node *last = nullptr, *nextStart = nullptr;
            for (Node *p = start; p != nullptr; p = p->next) {
                if (p->left) {
                    handle(last, p->left, nextStart);
                }
                if (p->right) {
                    handle(last, p->right, nextStart);
                }
            }
            start = nextStart;
        }
        return root;
    }
};

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii/solution/tian-chong-mei-ge-jie-dian-de-xia-yi-ge-you-ce-15/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

上边同样是只用一根指针不使用额外空间的方法。

核心的遍历逻辑还是一样的,就是把当前节点的子节点进行连接。

他这里的实现是如此的简洁,原因是他在最开始处理的时候就没有对节点连接进行分类,而是直接统一搞得。

如何统一的呢,还是对于题目的理解,你要把他们之间用next连起来,那分摊下来就是每个节点把自己的next指向合适的位置就得了,或者理解成,每个节点都被合适的next指向就得了。你不用两个都操心:你指向谁,谁指向你。

而这里我选用的是第一个,就是考虑指向谁,所以不断的需要往后找紧接着的是哪个节点。

题目选用的是第二个,就是让自己被指就行了,题目的巧妙之处就在于,利用了一根指针保存住上一个节点,因为这里的节点是从左至右逐一访问的,所以在访问下一个节点的时候用刚刚保存的节点的指针去->next = 当前节点  就行了。这样就实现了每一个节点都合理的被指的操作。

/*
// 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:
    void point(Node* &last,Node* &p, Node* &nextFirst){
        if(last){
            last->next = p;
        }
        if(nextFirst == nullptr){
            nextFirst = p;
        }
        last = p;
    }
    Node* connect(Node* root) {
        Node* first = root;
        while(first){
            Node* last = nullptr;
            Node* nextFirst = nullptr;
            for(Node* i = first; i != nullptr; i = i->next){
                if(i->left)point(last, i->left, nextFirst);
                if(i->right)point(last, i->right, nextFirst);
            }
            first = nextFirst;
        }
        return root;
    }
};

有一个注意点就是上边一定传引用,因为你是对指针本身改变,指针本身也就是那一串地址变化,所以你得用引用。

你之前印象中的传指针,可以把原来的改变,你是可以把指针指向的内容改变,这里是改变的指针!!!!!!!!

你可能感兴趣的