Description:
You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:
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,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Explanation: Given the above perfect 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, we need to populate the next pointers in each node to point to its next right node. Since the tree is a perfect binary tree, we can utilize this property to efficiently connect the nodes at each level.
We can solve this problem with a level-order traversal, using the next pointers to traverse the levels. However, to follow the constraint of using constant extra space, we will not use an explicit queue. Instead, we’ll use the already established next pointers to link the nodes at the next level.
# 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 None
# Start with the root of the tree
leftmost = root
while leftmost.left:
# Iterate over the nodes at the current level using the next pointers
head = leftmost
while head:
# Connect the left child to the right child
head.left.next = head.right
# Connect the right child to the next left child (if there is a next)
if head.next:
head.right.next = head.next.left
# Move to the next node at the current level
head = head.next
# Move to the leftmost node of the next level
leftmost = leftmost.left
return rootExplanation:
- Base Case: If the tree is empty, return
None. - Initialization: Start with the root node. This node is the leftmost node at the current level.
- Outer While Loop: Iterate as long as there are more levels to process (i.e.,
leftmost.leftexists). - Inner While Loop: Iterate over all nodes at the current level using their
nextpointers:- Connect Left to Right: For each node, connect its left child to its right child.
- Connect Right to Next Left: If there is a next node, connect the right child to the next node’s left child.
- Move to Next Node: Move to the next node at the current level using the
nextpointer.
- Move to Next Level: After finishing the current level, move to the leftmost node of the next level.
By using the next pointers to traverse the levels, we avoid using additional space for a queue or stack, adhering to the constant space constraint. The recursive nature of the traversal is handled implicitly by the structure of the tree.
Solution in 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 null;
}
// Start with the root of the tree
let leftmost = root;
while (leftmost.left) {
// Iterate over the nodes at the current level using the next pointers
let head = leftmost;
while (head) {
// Connect the left child to the right child
head.left.next = head.right;
// Connect the right child to the next left child (if there is a next)
if (head.next) {
head.right.next = head.next.left;
}
// Move to the next node at the current level
head = head.next;
}
// Move to the leftmost node of the next level
leftmost = leftmost.left;
}
return root;
};Solution in Java:
class Solution {
public Node connect(Node root) {
if (root == null) {
return null;
}
connectNodes(root);
return root;
}
private void connectNodes(Node node) {
if (node == null || node.left == null) {
return;
}
// Connect the left child to the right child
node.left.next = node.right;
// Connect the right child to the next node's left child
if (node.next != null) {
node.right.next = node.next.left;
}
// Recursively connect the subtree
connectNodes(node.left);
connectNodes(node.right);
}
}Solution in C#:
public class Solution {
public Node Connect(Node root) {
if (root == null) {
return null;
}
ConnectNodes(root);
return root;
}
private void ConnectNodes(Node node) {
if (node == null || node.left == null) {
return;
}
// Connect the left child to the right child
node.left.next = node.right;
// Connect the right child to the next node's left child
if (node.next != null) {
node.right.next = node.next.left;
}
// Recursively connect the subtree
ConnectNodes(node.left);
ConnectNodes(node.right);
}
}