/*
* @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