Description:
Given a binary tree
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.
Examples:
Example 1:
Input: root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]
Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.
Example 2:
Input: root = []
Output: []Solution in Python:
To solve this problem of connecting the next pointers in each node of a binary tree, we need to traverse the tree level-by-level (Breadth-First Search). We’ll use a queue to handle this traversal while maintaining the connections between nodes at the same level. This approach ensures that we use constant extra space (excluding the space required for the output and input data).
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
from collections import deque
class Solution:
def connect(self, root: 'Node') -> 'Node':
# Edge case: if the root is None, simply return None
if not root:
return None
# Initialize a queue for level order traversal
queue = deque([root])
# Process each level of the tree
while queue:
# Number of nodes at the current level
level_size = len(queue)
# Iterate through nodes at the current level
for i in range(level_size):
# Pop a node from the left of the queue
node = queue.popleft()
# If this is not the last node of the current level,
# set the next pointer to the next node in the queue
if i < level_size - 1:
node.next = queue[0]
# Add the left and right children of the node to the queue
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
# Return the root after all next pointers are connected
return rootExplanation:
- Node Definition: We define the
Nodeclass to includeval,left,right, andnextattributes. - Edge Case Handling: If the tree is empty (
rootisNone), we returnNoneimmediately. - Queue Initialization: We use a queue to facilitate level-order traversal. The root node is initially added to the queue.
- Level Order Traversal:
- We process the tree level by level.
- For each level, we determine the number of nodes (
level_size). - We iterate over each node in the current level, using a loop to process all nodes at that level.
- For each node, we set the
nextpointer to the node immediately to its right (if it exists). - We add the children of the current node to the queue for processing in the next level.
- Final Return: After connecting all the
nextpointers, we return therootnode.
This approach ensures that each node is processed only once, and the space complexity is kept constant (excluding the input and output) due to the use of the queue. The solution is efficient and adheres to the problem’s constraints.
Solution in Javascript:
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) {
// Edge case: if the root is null, simply return null
if (!root) {
return null;
}
// Initialize a queue for level-order traversal
const queue = [];
queue.push(root);
// Process each level of the tree
while (queue.length > 0) {
// Number of nodes at the current level
const levelSize = queue.length;
// Iterate through nodes at the current level
for (let i = 0; i < levelSize; i++) {
// Dequeue a node from the front of the queue
const node = queue.shift();
// If this is not the last node of the current level,
// set the next pointer to the next node in the queue
if (i < levelSize - 1) {
node.next = queue[0];
}
// Add the left and right children of the node to the queue
if (node.left) {
queue.push(node.left);
}
if (node.right) {
queue.push(node.right);
}
}
}
// Return the root after all next pointers are connected
return root;
};Solution in Java:
Java
class Solution {
public Node connect(Node root) {
if (root == null) {
return null;
}
// Start with the root node
Node leftmost = root;
// Iterate level by level
while (leftmost != null) {
// Iterate the current level
Node head = leftmost;
Node prev = null; // Previous node in the next level
leftmost = null; // The leftmost node in the next level
while (head != null) {
// Handle the left child
if (head.left != null) {
if (prev != null) {
prev.next = head.left;
} else {
leftmost = head.left;
}
prev = head.left;
}
// Handle the right child
if (head.right != null) {
if (prev != null) {
prev.next = head.right;
} else {
leftmost = head.right;
}
prev = head.right;
}
// Move to the next node in the current level
head = head.next;
}
}
return root;
}
}Solution in C#:
C#
public class Solution {
public Node Connect(Node root) {
if (root == null) {
return null;
}
// Start with the root node
Node leftmost = root;
// Iterate level by level
while (leftmost != null) {
// Traverse the current level
Node head = leftmost;
Node prev = null; // Previous node in the next level
leftmost = null; // The leftmost node in the next level
while (head != null) {
// Process the left child
if (head.left != null) {
if (prev != null) {
prev.next = head.left;
} else {
leftmost = head.left;
}
prev = head.left;
}
// Process the right child
if (head.right != null) {
if (prev != null) {
prev.next = head.right;
} else {
leftmost = head.right;
}
prev = head.right;
}
// Move to the next node in the current level
head = head.next;
}
}
return root;
}
}