/117. Populating Next Right Pointers in Each Node II
Previous|Next

117. Populating Next Right Pointers in Each Node II

Medium
Linked Lists57.2% acceptance

Given a binary tree where each node contains an integer value and has left, right, and next pointers, update each node's next pointer to point to its immediate right node on the same level. If there is no such node, set the next pointer to None. Return the root node after updating all next pointers. The tree may be empty. The next pointers are initially set to None.

Example 1

Input: TreeNode(10, TreeNode(5, TreeNode(2), TreeNode(7)), TreeNode(15, None, TreeNode(20)))

Output: TreeNode(10, TreeNode(5, TreeNode(2), TreeNode(7)), TreeNode(15, None, TreeNode(20)))

Explanation: After connecting next pointers: 10->None, 5->15, 2->7, 7->20, 15->None, 20->None.

Example 2

Input: TreeNode(1, TreeNode(2), TreeNode(3, TreeNode(4), None))

Output: TreeNode(1, TreeNode(2), TreeNode(3, TreeNode(4), None))

Explanation: After connecting next pointers: 1->None, 2->3, 3->None, 4->None.

Constraints

  • 0 <= number of nodes <= 6000
  • -100 <= node value <= 100
  • You may only use constant extra space (implicit recursion stack is allowed)
Python (current runtime)

Case 1

Input: TreeNode(8, TreeNode(4, None, TreeNode(6)), TreeNode(12, TreeNode(10), TreeNode(14)))

Expected: TreeNode(8, TreeNode(4, None, TreeNode(6)), TreeNode(12, TreeNode(10), TreeNode(14)))

Case 2

Input: TreeNode(5)

Expected: TreeNode(5)

Case 3

Input: None

Expected: None