题目链接：117. 填充每个节点的下一个右侧节点指针 II

题解：

上一题的进阶版，二叉树变得更加的普通！

题目简述：

给定一棵非常普通的二叉树，每个节点多一个next指针，我们需要将其指向同一行紧挨着的下一个节点！

要求空间O(1)

题解：

不要求空间则可以通过简单BFS实现！

和上一题思想类似： 不过这个题我么无法直接通过上一层来找到下一层的对应关系，但是我们可以对下一层进行构造横向链表！

  • 若下一层存在：构建虚拟头结点以及尾指针，进行尾插法形成下一层单链表
    • 若上一层节点左儿子存在，则尾插法插入该节点
    • 若上一层节点右儿子存在，则尾插法插入该节点
  • 走向下一层，cur = head->next，由于head为虚拟头节点

时间复杂度：同样每个节点遍历一次，为O(n)

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/*
// 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) return root;
        auto cur = root;
        while(cur){
            auto head = new Node(-1), tail = head;
            for(auto p = cur; p; p = p->next){
                if(p->left) tail = tail->next = p->left;
                if(p->right) tail = tail->next = p->right;
            }
            cur = head->next;
        }
        return root;
    }
};