NeetCode #470LC-426MediumTrees
← Back to All Problems#470 · #426 · Convert Binary Search Tree to Sorted Doubly Linked List(将二叉搜索树转化为排序的双向链表)
📌 Problem Statement & Constraints
Convert a binary search tree into a sorted circular doubly linked list in place, where
left is the predecessor and right is the successor. Return the smallest value's node. Constraints: the number of nodes is in [0, 2000], -1000 <= Node.val <= 1000.💡 Core Algorithmic Approaches
- An in-order traversal visits the nodes in ascending order, which is exactly the linked-list order.
- During the traversal, link each node's
leftto the previous node and the previous node'srightto it. - Remember the first node visited; at the end, close the circle by linking the first and last.
- The traversal is O(n) and the relinking happens in place.
💻 Benchmark Python3 Implementation
class Solution:
def treeToDoublyList(self, root: "Optional[Node]") -> "Optional[Node]":
if not root:
return None
self.first = None
self.last = None
def inorder(node: "Optional[Node]") -> None:
if not node:
return
inorder(node.left)
if self.last:
self.last.right = node # successor link
node.left = self.last # predecessor link
else:
self.first = node # the smallest node
self.last = node
inorder(node.right)
inorder(root)
# close the circle
self.first.left = self.last
self.last.right = self.first
return self.first⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one in-order traversal.
💾 Space Complexity
O(h) for the recursion stack.
⚠️ Interview Pitfalls & Follow-ups
- Forgetting to close the circle: the list must be circular, so the first and last nodes must be linked both ways.
- Setting
firstat every node: it must be set only for the very first (smallest) node. - Linking before recursing into the left subtree: the in-order order is what makes the links sorted.
- Assuming the tree is non-empty: an empty tree must return
None.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.