LeetCode 117. Populating Next Right Pointers in Each Node II

题目描述

给定一个二叉树

struct Node {
int val;
Node left;
Node
right;
Node *next;
}
填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。

初始状态下,所有 next 指针都被设置为 NULL。

你只能使用常量级额外空间。
使用递归解题也符合要求,本题中递归进程占用的栈空间不算做额外的空间复杂度。

tag

二叉树 BFS

样例

1
2
3
4
5
输入:{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":null,"next":null,"right":{"$id":"6","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}

输出:{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":null,"right":null,"val":7},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"6","left":null,"next":null,"right":{"$ref":"5"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"6"},"val":1}

解释:给定二叉树如图 A 所示,你的函数应该填充它的每个 next 指针,以指向其下一个右侧节点,如图 B 所示。

算法1

(BFS) O(n)
思路

从根节点开始宽度优先遍历,每次遍历一层,从左到右依次遍历每个节点。
遍历时维护下一层节点的链表。对于每个节点,依次判断它的左儿子和右儿子是否在存在,如果存在,则插入下一层链表的末尾。

复杂度分析:
python 代码
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
class :
def connect(self, root: 'Node') -> 'Node':
res = root

while root:
dummy = Node(0, None, None, None)

tail = dummy
while root:

if root.left:

tail.next = root.left
tail = tail.next

if root.right:

tail.next = root.right
tail = tail.next

root = root.next

tail.next = None
# dummy指向下一层开头节点的前一个节点
root = dummy.next

return res

算法2

(递归) O(n)
思路
复杂度分析:
python 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def connect(self, root: 'Node') -> 'Node':
if not root:
return None
if root.left and root.right:
root.left.next = root.right
_next = root.next
while _next and not _next.left and not _next.right and _next.next:
_next = _next.next
if _next:
if root.right:
root.right.next = _next.left if _next.left else _next.right
elif root.left:
root.left.next = _next.left if _next.left else _next.right

root.right = self.connect(root.right)
root.left = self.connect(root.left)
return root