Description

LeetCode 99

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
\
2

Output: [3,1,null,null,2]

3
/
1
\
2


Example 2:

Input: [3,1,4,null,null,2]

3
/ \
1   4
/
2

Output: [2,1,4,null,null,3]

2
/ \
1   4
/
3


• A solution using O(n) space is pretty straight forward.
• Could you devise a constant space solution?

Analysis

The core knowledge of this problem we must know is that in a binary search tree, the inorder traversal is a sorted increasing sequence. So the problem is to find two nodes that have been swapped from a sorted increasing sequence. But how can we find them with a constant space?

There are two conditions. The two nodes could be adjacent or not. We could use three node to record and set them as null. When we find a node that is larger than the next node. we should record the node as the first node and the next node as the second node. If we find this situation at the next time, we record the next node as the third node. If the third node is not null, that means the two nodes that have been swapped are not adjacent. So swap the first node and the third node. Otherwise, the two nodes are adjacent. Then swap the first node and the second node.

Solution

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
TreeNode x;
boolean xenable;
TreeNode node1,node2,node3;
public void recoverTree(TreeNode root) {
x=null;
node1=null;
node2=null;
node3=null;
xenable=false;
helper(root);
if(node3==null)
{
int tmp=node1.val;
node1.val=node2.val;
node2.val=tmp;
}
else
{
int tmp=node1.val;
node1.val=node3.val;
node3.val=tmp;
}
}
public void helper(TreeNode root)
{
if(root!=null)
{
helper(root.left);
if(xenable&&x.val>=root.val)
{
if(node1==null)
{
node1=x;
node2=root;
}
else node3=root;
}
else
{
xenable=true;
}
x=root;
helper(root.right);
}
}
}