[LeetCode每日一题]99. Recover Binary Search Tree

题目如下:

Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.

LeetCode-99 Recover Binary Search Tree 该题给定一棵二叉搜索树，树中正好有两个元素放反了，要求我们恢复这棵二叉搜索树。 首先让我们想一下BST的定义： （1）左子树上所有的值小于根节点； （2）柚子树上所有的值大于根节点； （3）BST的任意一棵子树也是BST。 BST有这样一条性质：按照中序遍历BST可得到一个升序序列。由此中序遍历该题的BST得到的序列中必然有两个数放反了，我们要做的便是找到这两个数所在的节点并交换他们。 代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    TreeNode biggerNode = null;  //放错的较大的节点
    TreeNode smallerNode = null; //放错的较小的节点
    TreeNode preNode = new TreeNode(Integer.MIN_VALUE); //用于比较的前驱节点，root节点没有前驱节点,所以该节点的值初始化为MIN_VALUE

    public void recoverTree(TreeNode root) {
        dfs(root);
        //交换两节点的值
        int temp = biggerNode.val;
        biggerNode.val = smallerNode.val;
        smallerNode.val = temp;
        return;
    }

    private void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.left);
        if (root.val < preNode.val) {
            if (biggerNode == null || biggerNode.val < preNode.val) {
                biggerNode = preNode;
            }
            if (smallerNode == null || root.val < smallerNode.val) {
                smallerNode = root;
            }
        }
        preNode = root;
        dfs(root.right);
        return;
    }
}

该算法每个节点访问一次，时间复杂度为O（n），开了三个全局变量，空间复杂度为O（1）。