Populating Next Right Pointers in Each Node
MediumP3Coding
You are given a perfect binary tree: every internal node has two children and all leaves are on the same level. Give each node a next pointer to the node immediately to its right on the same level, or to nothing for the last node of a level. The original task sets these pointers in place.
The test harness cannot build nodes with next, so the function receives the tree and returns an array instead: after you set the pointers, list the nodes in level order (left to right, top to bottom) and, for each one, output the value of the node its next points to, or -1 if it has none. You may assign node.next on the tree nodes you are given. Aim for O(1) extra space.
Example 1
- Input
- root = [1,2,3,4,5,6,7]
- Output
- [-1,3,-1,5,6,7,-1]
- Why
- Node 1 has no neighbour, 2 points to 3, 4 to 5, 5 to 6, 6 to 7, and 3 and 7 end their levels.
Example 2
- Input
- root = []
- Output
- []
Constraints
- 0 <= number of nodes <= 2^12 - 1
- The tree is perfect.
- 0 <= Node.val <= 1000
Hints
Give it a real attempt first. Run shows which examples fail.
Saved automatically
Run checks the 3 visible tests, Submit all 8. ⌘Enter runs, ⌘⇧Enter submits.