LeetCode刷题【99】恢复二叉搜索树

给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。

进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？

示例 1：

输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。

示例 2：

输入：root = [3,1,4,null,null,2]
输出：[2,1,4,null,null,3]
解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。

提示：

• 树上节点的数目在范围 [2, 1000] 内
• -231 <= Node.val <= 231 - 1

题解

关键信息“二叉搜索树”，重点在于二叉搜索树的一个特殊的特性，他的中序遍历的结果是递增的。那么本题就是应该利用这个特性来解决，在中序遍历的时候，对比当前节点和前驱节点的值，如果不是前驱节点小，当前节点大，那么说明这边是顺序有问题的。

注意，这里只能说明是有问题，拿具体的中序遍历结果来示意【1,2,6,4,5,3,7】,这里的6比后面的4大，并不能说明是6和4调换位置了，而是应当继续往后寻找，找到最后一个比当前6小的节点，才是和6调换了位置的节点。此处应当是3节点。

所以，代码：

class Solution {

    TreeNode preNode;
    TreeNode errorNode1;
    TreeNode errorNode2;
    public void recoverTree(TreeNode root) {
        dfs(root);
        int tmp = errorNode2.val;
        errorNode2.val = errorNode1.val;
        errorNode1.val = tmp;
    }
    
    
    private void dfs(TreeNode node){
        if (null == node){
            return;
        }
        dfs(node.left);
        //mid
        if (preNode!=null){
            if (preNode.val > node.val){
                if (errorNode2==null)errorNode2 = preNode;
                errorNode1 = node;
            }
        }

        //更新前序节点
        preNode = node;
        dfs(node.right);
    }
}

当然，最直接的就是像上面分析的那样，把中序遍历结果存下来，然后对这个结果遍历查找到调换了顺序的。也可以就像代码中这样的在中序遍历的时候根据前驱节点的值的情况来记录比较。