算法1

(中序遍历) $O(n)$

二叉搜索树的中序遍历就是一个已排序数组，
1.求树的中序遍历；
2.找到数组中被交换的数，用双指针；
3，在原树中修改被改变的值

时间复杂度

参考文献

java 代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public void recoverTree(TreeNode root) {
        //找到交换的节点，可以用中序遍历的性质找到其中序遍历的数组，然后看哪个节点被交换了
        List<Integer> q = new ArrayList<>();
        dfs(q,root);
        int i = 0;
        int j = q.size()-1;
        while(q.get(i)<q.get(i+1)) i++;
        while(q.get(j)>q.get(j-1)) j--;
        swapTree(root,q.get(i),q.get(j));
    }
    public void  dfs(List<Integer> q,TreeNode root){
        if(root==null) return;
        dfs(q,root.left);
        q.add(root.val);
        dfs(q,root.right);
    }
    public void swapTree(TreeNode root,int k,int g){
        Queue<TreeNode> mq = new LinkedList<>();
        mq.add(root);
        while(!mq.isEmpty()){
            TreeNode cur = mq.poll();
            if(cur.left!=null) mq.add(cur.left);
            if(cur.right!=null) mq.add(cur.right);
            if(cur.val == k) {cur.val=g;continue;}
            if(cur.val == g) cur.val=k;
        }
    }
}