Two elements of a binary search tree (BST) are swapped by mistake.Recover the tree without changing its structure.
public void recoverTree(TreeNode root) {
ArrayList<TreeNode> ary = new ArrayList<TreeNode>();
infixOrder(root, ary);
TreeNode errorNodeAry[] = new TreeNode[2];
int index = -1;
for (int i = 0; i < ary.size()-1; i++) {
if (ary.get(i).val>ary.get(i+1).val) {
errorNodeAry[0] = ary.get(i);
index = i;
break;
}
}
if (errorNodeAry[0]==null) {
errorNodeAry[0] = ary.get(ary.size()-1);
index = 0;
}
for (int i = index+2; i < ary.size(); i++) {
if (ary.get(i).val<ary.get(i-1).val) {
errorNodeAry[1] = ary.get(i);
break;
}
}
if (errorNodeAry[1]==null) {
errorNodeAry[1] = ary.get(index+1);
}
int temp = errorNodeAry[0].val;
errorNodeAry[0].val = errorNodeAry[1].val;
errorNodeAry[1].val = temp;
}
private void infixOrder(TreeNode node,ArrayList<TreeNode>ary) {
if (node == null) {
return;
}
infixOrder(node.left, ary);
ary.add(node);
infixOrder(node.right, ary);
}
