Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

递归法

思路

这道题是要求恢复一颗有两个元素调换错了的二叉查找树。中序遍历BST 然后找到逆序。有两种情况需要考虑:

1. 两个错位的节点是相邻的父子树关系, 那么找到第一个先序遍历逆序的两个节点

2. 两个错位的节点不是父子树关系, 这就是发生两次逆序的情况，那么这时候需要调换的元素应该是第一次逆序前面的元素，和第二次逆序后面的元素。

复杂度

时间O(n) 空间栈O(logn)

代码

TreeNode pre, first, second;
public void recoverTree(TreeNode root) {
    pre = null;
    first = null;
    second = null;
    inorder(root);
    if (first != null && second != null){
        int tem = first.val;//只调换val 不是node
        first.val = second.val;
        second.val = tem;
    }
}
private void inorder(TreeNode root){
    if (root == null){
        return;
    }
    inorder(root.left);
    if (pre == null){
        pre = root;//初始化pre
    } else {
        if (pre.val > root.val){
            if (first == null){
                first = pre;//第一个逆序点
            } 
            second = root;//如果相邻第一次就找全， 如果不相邻则遍历完后找到第二个逆序点
        }
        pre = root;//给pre赋值
    }
    inorder(root.right);
}