/*
 * @lc app=leetcode.cn id=99 lang=javascript
 *
 * [99] 恢复二叉搜索树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var recoverTree = function(root) {
    /**
     * 中序遍历的二叉搜索树数组整体上是有序递增的，出现乱序之后
     * 从第一个节点开始遍历 找到最大值，然后找到剩下所有升序
     * 里面的最小值，二者交换位置。
     */
    let firstMaxNode = null;
    let lastMinNode = null;
    let prevNode = new TreeNode(-Infinity); //保证二叉树前面那个节点很小很小
    let inorder = root => {
        if(!root) return;
        inorder(root.left)
        //记录下两个最值
        if(prevNode.val>root.val) {
            lastMinNode=root;
            if(!firstMaxNode)
            firstMaxNode=prevNode;
        }
        prevNode=root;
        inorder(root.right);
    }
    inorder(root);
    if(firstMaxNode&&lastMinNode) {
        //交换位置
        let temp = firstMaxNode.val;
        firstMaxNode.val = lastMinNode.val;
        lastMinNode.val= temp;
    }

};
// @lc code=end