【LeetCode】Day72-恢复二叉搜索树

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

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

class Solution {
    public void recoverTree(TreeNode root) {
        Stackstack=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
                second=root;
                if(first==null)
                    first=preNode;
                else
                    break;
            }
            preNode=root;
            root=root.right;
        }
        int tmp=first.val;
        first.val=second.val;
        second.val=tmp;
    }
}

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

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

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