[LeetCode]117. Populating Next Right Pointers in Each Node II

Problem

Given a binary tree

1
2
3
4
5
6
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Solution

想法是使用二叉树的层序遍历。在层序遍历中, 对每一层的next指针进行赋值。

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
35
36
37
38
39
40
41
42
/*
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;
Node* next;

Node() {}

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 nullptr;
queue<Node*> q;
q.push(root);

while (!q.empty()){//层序遍历的非递归形式
Node* pre = nullptr;//前驱节点
int size = q.size();
while (size--){
Node* cur = q.front();
q.pop();
if (cur->left) q.push(cur->left);
if (cur->right) q.push(cur->right);
if (pre) pre->next = cur;//如果不为空,设置next指针,指向当前节点
pre = cur;//pre指针更新
}
}

return root;
}
};

递归形式

需要注意的是,先对右子树进行连接,再对左子树连接;否则会出错。eg:

      2
   /     \
4         3

/ \ / \ 0 7 9 1 / / \ / \ 5 12 6 8 11 / 10

当遍历到7时,对7的左子树、右子树的next指针赋值时,当需要对6赋值时,因为7的兄弟还没有访问,不知道是谁,这时6的next指针赋值为null,但应该指向8.

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/*
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;
Node* next;

Node() {}

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 nullptr;
// 找兄弟节点的第一个孩子节点:左孩子不存在,找右孩子;左右孩子都不存在,换一个兄弟继续找
Node* p = root->next;

while (p){
if (p->left){
p = p->left;
break;
}
if (p->right){
p = p->right;
break;
}
p = p->next;// 换一个兄弟
}
// 开始连接: 顺序调换没有关系: 先对左指针,or先对右指针都可以
if (root->right) root->right->next = p;
if (root->left) root->left->next = (root->right ? root->right : p);

// 先连接右子树,在连接左子树;否则会出错---右边第一个兄弟没有孩子
connect(root->right);
connect(root->left);


return root;
}
};

常量空间

题目要求使用常量空间。这里继续对程序进行优化,主要优化方向就是减少空间的占用。这里利用一个变量来存储下层节点的起始位置,然后当本层节点的孩子节点赋值完成后,变更到保存节点的位置。

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
35
36
37
38
39
40
41
42
43
44
45
46
/*
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;
Node* next;

Node() {}

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* dummy = new Node(-1, nullptr, nullptr, nullptr), *cur = dummy, *head = root;
// dummy节点使得操作统一,不用判断是不是第一个节点
while (root){
// 当前节点的孩子进行赋值
if (root->left){
cur->next = root->left;
cur = cur->next;
}
if (root->right){
cur->next = root->right;
cur = cur->next;
}
// 访问兄弟节点
root = root->next;
if (!root){//如果为空,换一层
root = dummy->next;
dummy->next = nullptr;
cur = dummy;
}
}

return head;
}
};

References

https://www.cnblogs.com/grandyang/p/4290148.html

您的支持就是我更新的最大动力!谢谢!