Tree DFS
LC #99Hard
Recover Binary Search Tree
Tree DFS
AmazonGoogleMicrosoftProblem
Two nodes in a BST are swapped by mistake. Recover the tree without changing its structure.
treedfsbstin-order
Constraints
- ›2 ≤ number of nodes ≤ 1000
- ›-2³¹ ≤ node.val ≤ 2³¹-1
- ›O(1) space preferred (Morris traversal)
Example
Input
root = [1, 3, null, null, 2]Output
[3, 1, null, null, 2]Why
3 and 1 were swapped; in-order should be 1,2,3