NeetCode #444LC-99MediumTrees
← Back to All Problems#444 · #99 · Recover Binary Search Tree(恢复二叉搜索树)
📌 Problem Statement & Constraints
You are given the root of a binary search tree in which exactly two nodes were swapped by mistake. Recover the tree without changing its structure. Constraints: the number of nodes is in
[2, 1000], -2^31 <= Node.val <= 2^31 - 1.💡 Core Algorithmic Approaches
- An in-order traversal of a valid BST is strictly increasing, so the two swapped nodes appear as inversions in the traversal.
- Track the previous node; when
prev.val > node.val, an inversion has been found. - The first inversion's
previs the first misplaced node, and the last inversion'snodeis the second. - Swapping their values restores the BST. This works for both adjacent and non-adjacent swaps.
💻 Benchmark Python3 Implementation
class Solution:
def recoverTree(self, root: Optional[TreeNode]) -> None:
self.first = None
self.second = None
self.prev = None
def inorder(node: Optional[TreeNode]) -> None:
if not node:
return
inorder(node.left)
if self.prev and self.prev.val > node.val:
# the first inversion gives the larger node, the last gives the smaller
if self.first is None:
self.first = self.prev
self.second = node
self.prev = node
inorder(node.right)
inorder(root)
self.first.val, self.second.val = self.second.val, self.first.val⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one in-order traversal.
💾 Space Complexity
O(h) for the recursion stack. Morris traversal would give O(1).
⚠️ Interview Pitfalls & Follow-ups
- Swapping as soon as an inversion is found: for a non-adjacent swap there are two inversions, and the correct pair is the first inversion's larger node and the last inversion's smaller node.
- Assuming the swapped nodes are adjacent in value: they need not be.
- Comparing only adjacent values without tracking
firstandsecondseparately: both positions must be recorded. - Rebuilding the tree: the values are swapped in place, leaving the structure untouched.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.