Sponsored
Sponsored
This approach involves using a queue to perform a level order traversal of the tree. At each level of the tree, we'll connect the 'next' pointers of all nodes at that level. Since it is a perfect binary tree, each node at a level is directly followed by its sibling or by NULL if it is the last node at that level.
Time Complexity: O(N), where N is the number of nodes, since each node is processed once.
Space Complexity: O(1), as no extra space other than pointers is used—the perfect use of a constant space solution.
1function Node(val, left, right, next) {
2 this.val = val === undefined ? 0 : val;
3 this.left = left === undefined ? null : left;
4 this.right = right === undefined ? null : right;
5 this.next = next === undefined ? null : next;
6};
7
8var connect = function(root) {
9 if (!root) return null;
10 let current = root;
11 while (current.left !== null) {
12 let head = current;
13 while (head !== null) {
14 head.left.next = head.right;
15 if (head.next) {
16 head.right.next = head.next.left;
17 }
18 head = head.next;
19 }
20 current = current.left;
21 }
22 return root;
23};The JavaScript solution iterates through each level of the perfect binary tree using two pointers to establish connections across all level nodes and stops when the leaf nodes are reached.
The recursive method explores the tree depth-first and connects nodes level-wise. This approach effectively utilizes the call stack for traversal, aligning with the tree's inherent properties.
Time Complexity: O(N), which implies visiting each node once.
Space Complexity: O(logN) for recursion stack, since depth is proportional to the logarithm of node count.
1 public int val;
public Node left;
public Node right;
public Node next;
public Node() { }
public Node(int _val) { val = _val; }
}
public class Solution {
public Node Connect(Node root) {
if (root == null || root.left == null)
return root;
root.left.next = root.right;
if (root.next != null)
root.right.next = root.next.left;
Connect(root.left);
Connect(root.right);
return root;
}
}This C# recursive implementation handles each subtree similarly, employing the stack to manage the sequence of operations in node connectivity.