[leetcode-二叉查找树的修正]--99. Recover Binary Search Tree

绝地灬酷狼 2022-07-12 03:47 172阅读 0赞

Question 99. 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?
> 
> 中文：二叉查找树中有两个元素被交换了，导致不满足二叉查找树的定义。现在找出这两个结点并修复这个二叉查找树。
> 
> note: 使用O(n)空间复杂度可以很容易解决，但是可以使用常数的空间复杂度解决吗？

# O(n)空间复杂度实现方案 #

这里我先使用O(n)的空间复杂度解决，思路很简单。首先对二叉树做一个中序遍历，然后保存结点的中序序列。根据二叉排序树的value是升序的这个特点，然后找到被交换的两个结点在数组中的索引。然后交换这两个结点的value 即可。实现代码如下：

/** * @param root * @return */
    public static void recoverTree(TreeNode root) {
        //获取结点的中序排序
        List<TreeNode> res= new ArrayList<TreeNode>();
        inHelper(root, res);
    
        //将中序序列存入数组中
        TreeNode[] array = new TreeNode[res.size()];
        int i=0;
        for (TreeNode r : res){
            array[i++] = r;
        }
    
        //找到错误的两个元素的下标
        int low, hi;
        hi = low = 0;
        for(i=0; i<array.length; i++ ){
            if( i < array.length-1 && array[i].val > array[i+1].val){
                low = i;
                break;
            }
        }
        for(i=array.length-1; i>=0; i-- ){
            if( i >0  && array[i].val < array[i-1].val){
                hi = i;
                break;
            }
        }
    
        //将数组中两个结点的 value交换
        int temp=0;
        temp = array[low].val;
        array[low].val = array[hi].val;
        array[hi].val = temp;
    
        /*for (TreeNode ss : array){ System.out.println(ss.val); }*/
    }
    
    /** * 中序排序 * @param root * @param in */
    private static void inHelper(TreeNode root, List<TreeNode> in) {
        if(root==null) return;
        inHelper(root.left, in);
        in.add(root);
        inHelper(root.right,in);
    }

下面给出一个测试代码：

public static void main(String[] args) {
        TreeNode root = new TreeNode(10);
        root.left = new TreeNode(6);
        root.right = new TreeNode(8);
    
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(20);
    
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(23);
    
        Question99.recoverTree(root);
    
    }

这个测试用例中用到的树是：

10
        / \    6   8
      / \  /\  3 20 15 23

然后我输出修正后的value: 输出结果是：

3
    6
    8
    10
    15
    20
    23

可知结果正确。

本文完整的源码github地址：  
[https://github.com/leetcode-hust/leetcode/blob/master/louyuting/src/leetcode/Question99.java][https_github.com_leetcode-hust_leetcode_blob_master_louyuting_src_leetcode_Question99.java]

[https_github.com_leetcode-hust_leetcode_blob_master_louyuting_src_leetcode_Question99.java]: https://github.com/leetcode-hust/leetcode/blob/master/louyuting/src/leetcode/Question99.java