Recover Binary Search Tree
Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure, but by only swapping these two nodes.
Constraints:
- The number of nodes in the tree is in the range [1, 1000].
- 0 <= Node.val <= 1000
- Root is a valid binary search tree before swap.
Examples:
Input: [1, null, 2, null, null, 3, null, null, null, 4]
Output: [1, null, 2, null, null, 3, null, null, null, 4] after swapping node 2 and node 3
Explanation: The binary search tree is: 1 \ 2 \ 3 \ 4 After swapping node 2 and node 3, the binary search tree becomes: 1 \ 3 \ 2 \ 4
Solutions
Inorder traversal and swapping
The solution uses inorder traversal to find the two nodes that are in the wrong order. It keeps track of the previous node and checks if the current node's value is smaller than the previous node's value. If it is, it means that the current node and the previous node are the two nodes that need to be swapped.
class Solution:
def recoverTree(self, root:
TreeNode) -> None:
self.prev = None
self.big = None
self.small = None
self.inorder(root)
self.big.val, self.small.val = self.small.val, self.big.val
def inorder(self, root):
if not root:
return
self.inorder(root.left)
if self.prev and self.prev.val > root.val:
self.small = root
if not self.big:
self.big = self.prev
self.prev = root
self.inorder(root.right)Follow-up:
How would you solve this problem if you are not allowed to use any extra space?
