Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
解题思路：
先中序遍历找到mistake，然后替换即可，JAVA实现如下：
public void recoverTree(TreeNode root) {
List<Integer> list = inorderTraversal(root);
int left = 0, right = 0;
boolean first = true;
for (int i = 0; i < list.size(); i++) {
if (first && i != list.size() - 1 && list.get(i) >= list.get(i + 1)) {
left = list.get(i);
first = false;
}
if (!first && i != 0 && list.get(i) < list.get(i - 1)) {
right = list.get(i);
}
}
transformTreeNode(root, right, Integer.MAX_VALUE);
transformTreeNode(root, left, right);
transformTreeNode(root, right, left);
}
public static void transformTreeNode(TreeNode root, int souce, int target) {
if (root == null)
return;
if (root.val == souce) {
root.val = target;
return;
}
transformTreeNode(root.left, souce, target);
transformTreeNode(root.right, souce, target);
}
static public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
if (root == null)
return list;
if (root.left != null)
list.addAll(inorderTraversal(root.left));
list.add(root.val);
if (root.right != null)
list.addAll(inorderTraversal(root.right));
return list;
}