力扣(LeetCode)116. 填充每个节点的下一个右侧节点指针(C++)

模拟

这题可以直接操作根节点，我们保存根结点，用作最终返回值。

填充每个结点的 $next$ 指针，其实是树的层序遍历。由于 $next$ 指针的存在，我们可以做到 $O(1)$ 的空间复杂度。

算法:
从根结点出发，利用 $next$ 指针同层右移，每个结点的左儿子的 $next=$ 右儿子，右儿子的 $next=$ 下一结点的左儿子。

p->left->next = p->right;//左儿子的 next=右儿子
p->right->next = p->next->left;//右儿子的 next=下一结点的左儿子
1
2

一层遍历结束后， $root$ 走到左儿子，进入下一层遍历。

class Solution {
public:
    Node* connect(Node* root) {
        if(!root) return root;
        Node *temp = root;
        while(root->left){
            for(auto p = root;p;p = p ->next){
                p->left->next = p->right;
                if(p->next) p->right->next = p->next->left;
            }
            root = root->left;
        }
        return temp;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

1. 时间复杂度 : $O(n)$ ， $n$ 是结点个数 ，每个结点至多被遍历一次，时间复杂度 $O(n)$ 。
2. 空间复杂度 : $O(1)$ ， 只使用常量级空间 。

AC