99. Recover Binary Search Tree
这道题看起来很难,其实,做起来也很难。前提是你没有找到方法,哈哈。这道题考察的还是二叉树的中序遍历的性质:有序。这个性质可以帮助我们完美地解决这道题。很显然,如果一个数是二叉搜索树的话,中序遍历的结果是有序的。如果交换两个元素,这种有序性就会被破坏。因此,我们比较相邻的两个元素,如果有序性被破坏(不是升序),那么被交换的元素就在这。我们知道,我们将会发现两个地方的有序性被破坏。在第一处,是一个大的元素被交换过来,所以保存大的那一个。在第二处,是小的那一个被交换过来,所以保存小的那一个。找到两个元素之后,进行交换即可。
说到这,解法就呼之欲出了:对树进行中序遍历,一边遍历,一边比较。显然,自然是中序遍历,程序当然就有两种写法:递归式和非递归式。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private TreeNode pre = null;
private TreeNode first = null;//这里的定义和前面一样,即inorder中,第一个比下一个大的。
private TreeNode second = null;//这里定义不一样,即inorder中,最后一个比上一个小的。这种定义下,second一定不是null。
public void recoverTree(TreeNode root) {
inorder(root);
swap(first, second);
return;
}
private void swap(TreeNode first, TreeNode second){
int temp = first.val;
first.val = second.val;
second.val = temp;
return;
}
private void inorder(TreeNode root){
if (root == null){
return;
}
inorder(root.left);
if (pre != null && first == null && pre.val > root.val){
first = pre;
}
if (first != null && root.val < pre.val){//second会不断更新。知道最后一个。
second = root;
}
pre = root;
inorder(root.right);
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public void recoverTree(TreeNode root) {
if (root == null) { return; }
TreeNode pre = null, first = null, second = null;
Stack<TreeNode> stk = new Stack<>();
while (!stk.isEmpty() || root != null) {
while (root != null) {
stk.push(root);
root = root.left;
}
TreeNode cur = stk.pop();
if (pre != null && pre.val >= cur.val) {
if (first == null) {
first = pre;
}
if (first != null) {
second = cur;
}
}
root = cur.right;
pre = cur;
}
int tmp = first.val;
first.val = second.val;
second.val = tmp;
}
}