/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 of the modified tree. The tree may be incomplete (not perfect).

Example 1

Input: TreeNode(10, TreeNode(5, None, TreeNode(8)), TreeNode(15))

Output: TreeNode(10, TreeNode(5, None, TreeNode(8)), TreeNode(15))

Explanation: After connecting next pointers: 10->None, 5->15, 15->None, 8->None

Example 2

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

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

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

Example 3

Input: None

Output: None

Explanation: Empty tree remains unchanged.

Constraints

  • 0 <= number of nodes <= 6000
  • -100 <= node value <= 100
  • The input tree may be incomplete (not perfect)
Python (current runtime)

Case 1

Input: TreeNode(7, TreeNode(3, TreeNode(1), TreeNode(4)), TreeNode(9, None, TreeNode(11)))

Expected: TreeNode(7, TreeNode(3, TreeNode(1), TreeNode(4)), TreeNode(9, None, TreeNode(11)))

Case 2

Input: TreeNode(20, TreeNode(10), TreeNode(30, TreeNode(25), None))

Expected: TreeNode(20, TreeNode(10), TreeNode(30, TreeNode(25), None))

Case 3

Input: TreeNode(100)

Expected: TreeNode(100)