给定一个二叉树
Given a binary tree
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL
。
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
.
初始状态下,所有 next 指针都被设置为 NULL
。
Initially, all next pointers are set to NULL
.
进阶:
Follow up:
示例:
img
输入:root = [1,2,3,4,5,null,7]
输出:[1,#,2,3,#,4,5,7,#]
解释:给定二叉树如图 A 所示,你的函数应该填充它的每个 next 指针,以指向其下一个右侧节点,如图 B 所示。
提示:
6000
-100 <= node.val <= 100
Constraints:6000
.-100 <= node.val <= 100
与上一题的唯一区别就是该二叉树不是完美二叉树。对于完美二叉树的思路:
next
指针指向该结点的右孩子next
指针指向该结点的 next
结点的左孩子不再适用,因为一个结点可能没有左孩子或者没有右孩子。只需稍微转变一下思路即可:
先设置一个头结点 temp
,作为每层的最左侧结点。再设置一个前驱结点 prev = temp
,该结点的 next
指针指向最邻近的右侧结点,然后刷新前驱结点:prev = prev.next
。继续查找 prev
结点最邻近的右侧结点,重复上述操作,直到该层结束。而此时 头结点 temp.next
就是下一层的最左侧结点。
class Solution {
public Node connect(Node root) {
if (root == null)
return root;
Node temp = new Node(0); // 虚拟头结点
Node curr = root, prev = temp; // 当前结点和前驱结点
while (curr != null) {
if (curr.left != null) {
prev.next = curr.left;
prev = prev.next;
}
if (curr.right != null) {
prev.next = curr.right;
prev = prev.next;
}
curr = curr.next;
// curr 为 null 时,该层连接完成。
if (curr == null) {
curr = temp.next; // 当前结点改为下一层的最左侧结点
temp.next = null; // 虚拟结点 next 指针指向 null
prev = temp; // 前驱结点重新设置为虚拟头结点
}
}
return root;
}
}
class Solution:
def connect(self, root: 'Node') -> 'Node':
if not root:
return root
temp = Node(0) # 虚拟头结点
prev,curr = temp,root # 当前结点和前驱结点
while curr:
if curr.left:
prev.next = curr.left
prev = prev.next
if curr.right:
prev.next = curr.right
prev = prev.next
curr = curr.next
# curr 为 null 时,该层连接完成
if not curr:
curr = temp.next # 当前结点改为下一层的最左侧结点
temp.next = None # 虚拟结点 next 指针指向 null
prev = temp # 前驱结点重新设置为虚拟头结点
return root