题目

99. 恢复二叉搜索树【中等】

题解

沿用昨天的98. 验证二叉搜索树的方法，中序遍历序一定是升序的，所以中序遍历一次，找到两个错位的结点，交换他俩的值。
如果有一个降序对，说明该两个node需交换；若有两个降序对，说明第一对的前一个node和第二对的后一个node需要交换。

class Solution {public void recoverTree(TreeNode root) {Stack<TreeNode>stack=new Stack<>();TreeNode preNode=null;//前一个结点TreeNode first=null;//第一个错位结点TreeNode second=null;//第二个错位结点while(!stack.empty()||root!=null){while(root!=null){stack.push(root);root=root.left;}root=stack.pop();//找降序对if(preNode!=null&&root.val<preNode.val){second=root;if(first==null)first=preNode;elsebreak;}preNode=root;root=root.right;}int tmp=first.val;first.val=second.val;second.val=tmp;}
}

时间复杂度：$O(n)$

空间复杂度：$O(h)$，中序遍历的时候栈的深度取决于二叉搜索树的高度。

p.s 咋感觉树的题比动态规划还难呢，代码平均下来确实比动态规划长，但是逻辑稍微简单些