Recover Binary Search Tree Problem: 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.
Input: root = [1,3,null,null,2] Output: [3,1,null,null,2]
Table of Contents
Problem Solution In Python
class Solution:
def recoverTree(self, root: TreeNode) -> None:
self.first, self.second, self.prev = None, None, TreeNode(float('-inf'))
def inorder(node):
if node:
inorder(node.left)
if self.prev.val >= node.val:
if not self.first:
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
Problem Solution In Java
class Solution {
ArrayList<Integer> list=new ArrayList<Integer>();
int count=0;
public void InOrder(TreeNode root)
{
if(root!=null)
{
InOrder(root.left);
if(list.get(count)!=root.val)
{
root.val=list.get(count);
}
count++;
InOrder(root.right);
}
}
public void recoverTree(TreeNode root)
{
Stack<TreeNode> stck=new Stack<TreeNode>();
int flag=0;
TreeNode current=root;
while(flag!=1)
{
if(current!=null)
{
stck.push(current);
current=current.left;
}
else
{
if(stck.empty())
{
flag=1;
}
else
{
current=stck.pop();
list.add(current.val);
current=current.right;
}
}
}
Collections.sort(list);
InOrder(root);
}
}
Problem Solution In C++
class Solution {
public:
void fun(TreeNode* root, TreeNode*&first, TreeNode*&mid, TreeNode*&last, TreeNode*&prev)
{
if(!root)
return;
fun(root->left,first,mid,last,prev);
if(prev && root->val <prev->val)
{
if(!first)
{
first = prev;
mid = root;
}
else last = root;
}
prev = root;
fun(root->right,first,mid,last,prev);
}
void recoverTree(TreeNode* root){
if(!root)
return ;
TreeNode* first = NULL, *last = NULL, *mid = NULL, *prev = NULL;
fun(root,first,mid,last,prev);
if(last)
swap(last->val,first->val);
else swap(first->val,mid->val);
}
};
Problem Solution In C
void recoverTree_r(struct TreeNode* root, struct TreeNode** fNode,
struct TreeNode** sNode, struct TreeNode** pNode){
if(root == NULL)
return;
recoverTree_r(root->left, fNode, sNode, pNode);
if(*pNode == NULL)
*pNode = root;
if((*pNode)->val > root->val) {
if(*fNode == NULL)
*fNode = *pNode;
*sNode = root;
}
*pNode = root;
recoverTree_r(root->right, fNode, sNode, pNode);
}
void recoverTree(struct TreeNode* root){
struct TreeNode* fNode = NULL, *sNode = NULL, *pNode = NULL;
recoverTree_r(root, &fNode, &sNode, &pNode);
int t = fNode->val;
fNode->val = sNode->val;
sNode->val = t;
return;
}