问题描述
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
解决思路
递归思路。
中序遍历的过程中，第一个违反顺序的节点一定是错误节点的其中一个；第二个违反顺序的节点的下一个节点是另外一个错误节点。
程序
public class RecoverBST {
private TreeNode pre = null;
private TreeNode n1 = null;
private TreeNode n2 = null;
public void recoverBST(TreeNode root) {
if (root == null) {
return;
}
inorderTraversal(root);
if (n1 != null && n2 != null) {
int tmp = n1.val;
n1.val = n2.val;
n2.val = tmp;
}
}
private void inorderTraversal(TreeNode root) {
if (root==null) {
return;
}
inorderTraversal(root.left);
if (pre != null && pre.val > root.val) {
n2 = root; // second error node‘s next
if (n1 == null) {
n1 = pre; // first error node
}
}
pre = root;
inorderTraversal(root.right);
}
}
原文：http://www.cnblogs.com/harrygogo/p/4654078.html