leetcode实战-99. Recover Binary Search Tree

写这篇文章的目的很单纯，就是来炫耀的，或者说展示下自己写算法的思路。

题目

99. Recover Binary Search Tree

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

Recover the tree without changing its structure.

代码块不贴了，简单解释下。

找出这个二叉搜索树中顺序错误的两个，不要改变树的结构。

这种BST按照中序遍历就能得到正确的大小顺序，如果有错误的，那么结果很容易得到了。

换句话说，中序遍历跑一边，交换一下错误的两个节点val就可以了。

所以问题就转换成了怎么找出2个顺序错误的节点。

下面就用代码说明问题是如何解决的。请按代码中1234的顺序查看

    public void recoverTree(TreeNode root) {
//        8.所以就如同设计，正向遍历找到第一个，反向遍历找到第二个，做交换。
        TreeNode first = recoverTreeHelper(root, new LinkedList<>(), true);
        TreeNode last = recoverTreeHelper(root, new LinkedList<>(), false);
        int temp = first.val;
        first.val = last.val;
        last.val = temp;
    }

    /*
    1.辅助方法，实现一个标准的中序遍历，见==部分,逻辑为递归左树，处理节点，递归右树
     */
    public TreeNode recoverTreeHelper(TreeNode root, LinkedList<TreeNode> sort, Boolean order) {
        /*
        4.这里我做了一个处理，order==true的时候是正向遍历，order==false的时候是反向遍历。
        原因是这样的，正向遍历，第一个顺序错误的绝对是要交换的值，反向遍历，第一个顺序错误的绝对是要交换的值。
        也就是说，只要找到一个顺序错误的，就直接跳出循环。
        这种处理的原因是：考虑【3,2,1】和【1,3,2,4】两个错误的BST，正向遍历，第一个点很好找（查找条件是错误排序的第一个点）。而【3，2,1】中第二个点不好找（有好几个错误的排序点），利用正向查第一个，反相查第一个可以很好的屏蔽这个问题。
         */
        TreeNode firstNode;
        TreeNode lastNode;
        if (order) {
            firstNode = root.left;
            lastNode = root.right;
        } else {
            firstNode = root.right;
            lastNode = root.left;
        }
        //==================================
        if (firstNode != null) {
            //5.所以我在这里，做了一个处理，直接利用辅助方法的返回值，只要找到了非空，即找到了一个顺序错误的treenode
            // ，就直接会把非空值一层一层传播到第一个调用的函数
            TreeNode left;
            if ((left = recoverTreeHelper(firstNode, sort, order)) != null) {
                return left;
            }
        }
        //===================================
        /*
         2.利用一个链表，缓存遍历的数据，即用这种入参的链表，拿到深层递归过程中的返回值。
         由于当前的函数，既要拿到顺序错误的节点，又要临时缓存几个排序的内容，所以选择一个list作为临时的变量。
         选择LinkedList而非List的原因是：我只需要比较当前节点和上一个节点 2个节点就行了，链表的API方便一点
         */
        sort.add(root);
        //3.所以我在这个位置移除掉多余的节点，保持链表只有2个，因为之前的顺序都是正确的，没有任何利用的价值。我需要的只是最近两个错误排序的节点
        if (sort.size() == 3) {
            sort.removeFirst();
        }
        if (sort.size() == 2) {
            //6.从前往后查，和从后往前查，需要比较的内容是不一样的，这里边就利用order做了一个判断，
            // 再加上链表中肯定只有2个值，做了个比较，返回错误的节点。由此开始传播return的内容。
            if (order && sort.getFirst().val > sort.getLast().val) {
                //7.考虑到要做val的交换，所以选择了返回TreeNode，所以在链表中也直接缓存了TreeNode，没有只记录val
                return sort.getFirst();
            } else if (!order && sort.getFirst().val < sort.getLast().val) {
                return sort.getFirst();
            }
        }
        //====================================
        if (lastNode != null) {
            TreeNode right;
            if ((right = recoverTreeHelper(lastNode, sort, order)) != null) {
                return right;
            }
        }
        //====================================
        return null;
    }

代码的思路就是这样，还是非常清晰的。用到了一些之前学到的技巧。如：

中序遍历
在条件判断中，递归方法，并把返回值传递出去，从而终止后续的递归过程
链表的FIFO队列
在条件判断中赋值——从HashMap源码学的小技巧

虽然提交了之后，虽然一遍通过，但速度并不是最快的。一些优化的思路还是知道的，但是没有做。

比方说，链表可以用 TreeNode[2]替代，手动实现下链表中的内容，速度应该会更快一些。
像其他人那样直接用全局变量做缓存也是可以的，只不过没想这么做。

希望这种做法能给大家带来一些启发。