Here, We see Recover Binary Search Tree LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.
List of all LeetCode Solution
![Recover Binary Search Tree LeetCode Solution](https://i0.wp.com/totheinnovation.com/wp-content/uploads/2024/02/LeetCode-Problem-Solution.png?resize=200%2C200&ssl=1)
Recover Binary Search Tree LeetCode Solution
Table of Contents
Problem Statement
You are given the root
of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.
Example 1: Input: root = [1,3,null,null,2] Output: [3,1,null,null,2] Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid. Example 2: Input: root = [3,1,4,null,null,2] Output: [2,1,4,null,null,3] Explanation: 2 cannot be in the right subtree of 3 because 2 < 3. Swapping 2 and 3 makes the BST valid.
Recover Binary Search Tree Leetcode Solution C++
class Solution {
private:
void markTree(TreeNode* root, TreeNode*& prev, TreeNode*& first, TreeNode*& end) {
if (!root) return;
markTree(root->left, prev, first, end);
if (prev) {
if (root->val < prev->val) {
if (!first) {
first = prev;
}
end = root;
}
}
prev = root;
markTree(root->right, prev, first, end);
}
public:
void recoverTree(TreeNode* root) {
TreeNode *prev = nullptr, *first = nullptr, *end = nullptr;
markTree(root, prev, first, end);
swap(first->val, end->val);
return;
}
};
Code language: PHP (php)
Recover Binary Search Tree Leetcode Solution Java
class Solution {
public void recoverTree(TreeNode root) {
TreeNode first = null;
TreeNode second = null;
TreeNode prev = null;
boolean swaped = false;
while(root!=null){
if(root.left==null){
if(prev!=null){
if(root.val<prev.val){
if(first==null){
first = prev;
second = root;
}else{
swap(first,root);
swaped = true;
}
}
}
prev = root;
root = root.right;
}else{
TreeNode cur = root;
TreeNode left = root.left;
while(left.right!=null&&left.right!=cur){
left = left.right;
}
if(left.right==null){
left.right = cur;
root = root.left;
}else{
if(prev!=null){
if(root.val<prev.val){
if(first==null){
first = prev;
second = root;
}else{
swap(first,root);
swaped = true;
}
}
}
left.right = null;
prev = root;
root = root.right;
}
}
}
if(!swaped){
swap(first,second);
}
}
public void swap(TreeNode a,TreeNode b){
int tmp = a.val;
a.val = b.val;
b.val = tmp;
}
}
Code language: JavaScript (javascript)
Recover Binary Search Tree Leetcode Solution JavaScript
var recoverTree = function(root) {
let first = null;
let last = null;
let prev = null;
function dfs (node) {
if (!node) return;
dfs (node.left);
if (prev && node.val < prev.val){
if (first === null) first = prev;
last = node;
}
prev = node;
dfs (node.right);
}
dfs(root, null)
let temp = first.val;
first.val = last.val;
last.val = temp
return root;
};
Code language: JavaScript (javascript)
Recover Binary Search Tree Leetcode Solution Python
class Solution(object):
def recoverTree(self, root):
x, y = self.forward(root, []), self.backward(root, [])
x.val, y.val = y.val, x.val
return root
def forward(self, root, n):
if root is None:
return
ret = self.forward(root.left, n)
if ret:
return ret
if not n:
n.append(root)
elif root.val < n[0].val:
return n[0]
else:
n[0] = root
ret = self.forward(root.right, n)
if ret:
return ret
def backward(self, root, n):
if root is None:
return
ret = self.backward(root.right, n)
if ret:
return ret
if not n:
n.append(root)
elif root.val > n[0].val:
return n[0]
else:
n[0] = root
ret = self.backward(root.left, n)
if ret:
return ret
Code language: HTML, XML (xml)