Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:

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

分析：http://www.cnblogs.com/yuzhangcmu/p/4208319.html

具体的思路，还是通过中序遍历，只不过，不需要存储每个节点，只需要存一个前驱即可。

例如1,4,3,2,5,6

1.当我们读到4的时候，发现是正序的，不做处理

2.但是遇到3时，发现逆序，将4存为第一个错误节点，3存为第二个错误节点

3.继续往后，发现3，2又是逆序了，那么将第2个错误节点更新为2

如果是这样的序列：1,4,3,5,6同上，得到逆序的两个节点为4和3。

========================================

这里我们补充一下，为什么要替换第二个节点而不是第一个节点：
e.g. The correct BST is below:

The inorder traversal is : 1 3 4 6 7 8 10 13 14

Find the place which the order is wrong.
        Wrong order: 1 3 8 6 7 4 10 13 14
        FIND:              8 6
        Then we find:         7 4
        8, 6 是错误的序列, 但是，7，4也是错误的序列。
        因为8，6前面的序列是正确的，所以8，6一定是后面的序列交换来的。
        而后面的是比较大的数字，也就是说8一定是被交换过来的。而7，4
        中也应该是小的数字4是前面交换过来的。

用反证法来证明：
        假设：6是后面交换过来的
        推论: 那么8比6还大，那么8应该也是后面交换来的，
        这样起码有3个错误的数字了
        而题目是2个错误的数字，得证，只应该是8是交换过来的。
结论就是：我们需要交换的是：8， 4.

 public class Solution {

     TreeNode pre = null, first = null,second = null;

     public void recoverTree(TreeNode root) {

         inOrder(root);

         int tmp = first.val;

         first.val = second.val;

         second.val = tmp;

     }

     public void inOrder(TreeNode root) {

         if (root == null) return;

         inOrder(root.left);

         if (pre != null && pre.val > root.val) {

             if (first == null) {

                 first = pre;

                 second = root;

             } else {

                 second = root;

             }

         }

         pre = root;

         inOrder(root.right);

     }

 }

巴特西

Recover Binary Search Tree

最新文章

热门文章