116. Populating Next Right Pointers in Each Node
給定一棵完美的二元樹，其中所有的葉節點都在同一層，且每個父節點都有兩個子節點。這棵二元樹有以下定義：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充每個節點的 next 指針，使其指向其右側的下一個節點。如果沒有右側的下一個節點，則將 next 指針設置為 NULL。
最初，所有的 next 指針都設置為 NULL。
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: 'Optional[Node]') -> 'Optional[Node]':
if not root:
return root
# Start with the root node
leftmost = root
while leftmost.left:
# Iterate over the nodes at the current level
head = leftmost
while head:
# Connect the left and right children
head.left.next = head.right
# Connect the right child to the next subtree's left child if available
if head.next:
head.right.next = head.next.left
# Move to the next node in the current level
head = head.next
# Move to the leftmost node of the next level
leftmost = leftmost.left
return root
18.10MB, 57ms
C++
class Solution {
public:
Node* connect(Node* root) {
if (!root) {
return root;
}
// Start with the root node
Node* leftmost = root;
while (leftmost->left) {
// Iterate over the nodes at the current level
Node* head = leftmost;
while (head) {
// Connect the left and right children
head->left->next = head->right;
// Connect the right child to the next subtree's left child if available
if (head->next) {
head->right->next = head->next->left;
}
// Move to the next node in the current level
head = head->next;
}
// Move to the leftmost node of the next level
leftmost = leftmost->left;
}
return root;
}
};
17.39MB, 13ms
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.left) {
// Iterate over the nodes at the current level
let head = leftmost;
while (head) {
// Connect the left and right children
head.left.next = head.right;
// Connect the right child to the next subtree's left child if available
if (head.next) {
head.right.next = head.next.left;
}
// Move to the next node in the current level
head = head.next;
}
// Move to the leftmost node of the next level
leftmost = leftmost.left;
}
return root;
};
52.95MB, 56ms
