Recover Binary Search Tree
Description
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Example 1:
Input: [1,3,null,null,2]1 / 3
2Output: [3,1,null,null,2]
3 / 1
2
Example 2:
Input: [3,1,4,null,null,2]3 /
1 4 / 2Output: [2,1,4,null,null,3]
2 /
1 4 / 3
Follow up:
- A solution using O(n) space is pretty straight forward.
- Could you devise a constant space solution?
Solution(javascript)
const recoverTree = function (root) {
let first = null
let second = null
let prev = null
const aux = (node) => {
if (node) {
aux(node.left)
if (prev && prev.val > node.val) {
if (!first) {
first = prev
second = node
} else {
second = node
}
}
prev = node
aux(node.right)
}
}
aux(root)
if (first && second) {
const temp = first.val
first.val = second.val
second.val = temp
}
}