Populating Next Right Pointers in Each Node II
The key idea
Once a level is fully wired, its
next pointers form a singly linked list you can walk left to right. While walking that level, stitch the children of each node onto a new linked list for the next level using a dummy head and a moving tail. This lets you reach every node of the next level without a queue, so the traversal uses only O(1) extra space.Problem
You are given a binary tree where each node has an extra next pointer. Populate every next pointer so it points to the node immediately to its right on the same level. If there is no node to the right, set next to null.
Unlike the perfect-tree version, this tree is not necessarily complete, so a level can have gaps. Initially every next pointer is set to null.
You may only use constant extra space. The recursion stack of an implicit recursive solution does not count as extra space for this problem.
Constraints
- The number of nodes in the tree is in the range
[0, 6000]. -100 <= Node.val <= 100
Examples
Input: root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]
Input: root = []
Output: []
Complexity
Time: O(n) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Tree / Recursion problems
- Balanced Binary TreeEASY
- Binary Tree CamerasHARD
- Binary Tree Inorder TraversalEASY
- Binary Tree Maximum Path SumHARD
- Binary Tree PathsEASY
- Binary Tree Postorder TraversalEASY
- Binary Tree Preorder TraversalEASY
- House Robber IIIMEDIUM
- Construct Binary Tree from Inorder and Postorder TraversalMEDIUM
- Construct Binary Tree from Preorder and Inorder TraversalMEDIUM
- Convert BST to Greater TreeMEDIUM
- Count Complete Tree NodesEASY