leetcode: 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?

原问题链接：https://leetcode.com/problems/recover-binary-search-tree/

 

问题分析

　　对于一棵二叉搜索树来说，如果它里面有两个节点的位置发生了交换，那么从它本身的性质来说，它这两个交换后的节点可能会出现每个节点在新的位置和它的左右子节点之间关系不符合原来的定义了。

　　这个时候，一个二叉搜索树的重要性质可以在这里起到大的作用。对于它来说，如果进行中序遍历的话，得到的结果是一个排序后递增的序列。可是如果我们交换了其中两个元素的话，里面就会有两个元素不符合递增的特性。

　　所以，我们可以通过中序遍历的时候将遍历过的所有元素加入到一个列表中。然后在结果列表里查找这两个元素就可以了。

　　那么，该怎么找这两个元素呢？因为交换了这两个元素之后，必然是一个大的元素放到了前面而一个小的元素放到了后面。所以我们从列表的第二个元素开始，每次比较当前元素和它的前一个元素。如果前一个元素比当前元素大，说明找到了这个大的元素。所以我们找到的第一个不符合条件的元素就是那个从后面被交换到前面的元素。而那个被前面交换到后面的元素则是最后一个不符合递增属性的元素。

　　找到这两个元素之后，我们交换设置这两个元素的值就可以了。详细的代码实现如下：

 

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void recoverTree(TreeNode root) {
        List<TreeNode> list = new ArrayList<>();
        traverse(root, list);
        int max = -1, min = -1;
        for(int i = 1; i < list.size(); i++) {
            if(list.get(i).val < list.get(i - 1).val) {
                max = i - 1;
                break;
            }
        }
        for(int i = max + 1; i < list.size(); i++) {
            if(list.get(i).val < list.get(i - 1).val)
                min = i;
        }
        if(max == -1 || min == -1) return;
        int temp = list.get(max).val;
        list.get(max).val = list.get(min).val;
        list.get(min).val = temp;
    }
    
    private void traverse(TreeNode node, List<TreeNode> list) {
        if(node == null) return;
        if(node.left != null) traverse(node.left, list);
        list.add(node);
        if(node.right != null) traverse(node.right, list);
    }
}