117. Populating Next Right Pointers in Each Node II
給定一棵二元樹：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充每個節點的 next 指針，使其指向其右側的下一個節點。如果沒有右側的下一個節點，則將 next 指針設置為 NULL。
最初，所有的 next 指針都設置為 NULL。
範例：
輸入：root = [1,2,3,4,5,null,7] 輸出：[1,#,2,3,#,4,5,7,#] 解釋：給定上面的二元樹（圖A），你的函數應該填充每個 next 指針，使其指向其右側的下一個節點，就像在圖B中一樣。序列化的輸出是按 next 指針連接的層次遍歷順序，每層的結尾用 # 表示。
Python
# Definition for a Node.
class Node:
def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
self.val = val
self.left = left
self.right = right
self.next = next
class Solution:
def connect(self, root: 'Node') -> 'Node':
if not root:
return root
# Start with the root node
leftmost = root
while leftmost:
# Traverse the current level and setup the next pointers for the next level
current = leftmost
prev = None
leftmost = None
while current:
for child in [current.left, current.right]:
if child:
if prev:
prev.next = child
else:
leftmost = child
prev = child
current = current.next
return root
17,74MB, 51ms
C++
class Solution {
public:
Node* connect(Node* root) {
if (!root) {
return root;
}
// Start with the root node
Node* leftmost = root;
while (leftmost) {
Node* current = leftmost;
Node* prev = nullptr;
leftmost = nullptr;
while (current) {
if (current->left) {
if (prev) {
prev->next = current->left;
} else {
leftmost = current->left;
}
prev = current->left;
}
if (current->right) {
if (prev) {
prev->next = current->right;
} else {
leftmost = current->right;
}
prev = current->right;
}
current = current->next;
}
}
return root;
}
};
17.09MB, 11ms
Javascript
/**
* // Definition for a _Node.
* function _Node(val, left, right, next) {
* this.val = val === undefined ? null : val;
* this.left = left === undefined ? null : left;
* this.right = right === undefined ? null : right;
* this.next = next === undefined ? null : next;
* };
*/
/**
* @param {_Node} root
* @return {_Node}
*/
var connect = function(root) {
if (!root) {
return root;
}
// Start with the root node
let leftmost = root;
while (leftmost) {
let current = leftmost;
let prev = null;
leftmost = null;
while (current) {
if (current.left) {
if (prev) {
prev.next = current.left;
} else {
leftmost = current.left;
}
prev = current.left;
}
if (current.right) {
if (prev) {
prev.next = current.right;
} else {
leftmost = current.right;
}
prev = current.right;
}
current = current.next;
}
}
return root;
};
52.90MB, 65ms
