题目描述

二叉搜索树中的两个节点被错误地交换。

请在不改变其结构的情况下，恢复这棵树。

样例

输入: [1,3,null,null,2]

   1
  /
 3
  \
   2

输出: [3,1,null,null,2]

   3
  /
 1
  \
   2

输入: [3,1,4,null,null,2]

  3
 / \
1   4
   /
  2

输出: [2,1,4,null,null,3]

  2
 / \
1   4
   /
  3

进阶:

• 使用 O(n) 空间复杂度的解法很容易实现。
• 你能想出一个只使用常数空间的解决方案吗？

算法分析

• 两个错误的结点的关键点是可以形成逆序对，通过递归或者迭代的方式将整棵树的中序遍历排列出来，并且将两个错误的结点找出来，再将两个结点的值继续交换

时间复杂度 $O(n)$

空间复杂度 $O(n)$

空间复杂度是常数的解法： y总的题解

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 {
    static List<TreeNode> list = new ArrayList<TreeNode>();
    static void dfs(TreeNode root)
    {
        if(root != null)
        {
            dfs(root.left);
            list.add(root);
            dfs(root.right);
        }
    }
    public void recoverTree(TreeNode root) {
        list.clear();
        dfs(root);
        TreeNode a = null;
        TreeNode b = null;
        for(int i = 0;i < list.size() - 1;i ++) {
            if(list.get(i).val > list.get(i+1).val) {
                b = list.get(i + 1);
                if(a == null) {
                    a = list.get(i);
                }
            }
        }
        //交换
        int t = a.val;
        a.val = b.val;
        b.val = t;
    }
}