99. 恢复二叉搜索树

• 考虑两个节点被错误地交换后对原二叉搜索树造成了什么影响？

• 对于二叉搜索树，我们知道如果对其进行中序遍历，得到的值序列是递增有序的，而如果我们错误地交换了两个节点，等价于在这个值序列中交换了两个值，破坏了值序列的递增性。 ```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> nums = new ArrayList();
    // 中序遍历该二叉树的结果
    inorder(root, nums);
    // 找出错误交换的2个数
    int[] swapped = findTwoSwapped(nums);
    // 恢复2个数
    recover(root, 2, swapped[0], swapped[1]);

    }

    // 中序遍历该二叉树，并保存结果 public void inorder(TreeNode root, List nums) {

    if (root == null) {
        return;
    }
    inorder(root.left, nums);
    nums.add(root.val);
    inorder(root.right, nums);
    

    }

    // 找到升序序列中位置错误的2个数 public int[] findTwoSwapped(List nums) {

    // 发现的非升序的位置数
    int count = 0;
    int x = -1, y = -1;
    for (int i = 0; i < nums.size() - 1; i++) {
        if (nums.get(i) > nums.get(i + 1)) {
            // 非升序的位置加1
            count++;
            if (count == 1) {
                x = nums.get(i);
                y = nums.get(i + 1);
            } else if (count == 2) {
                y = nums.get(i + 1);
                break;
            }
        }
    }
    return new int[] {x, y};
    

    }

    // 恢复二叉树中错位的2个数 public void recover(TreeNode root, int count, int x, int y) {

    if (root == null || count == 0) {
        return;
    }
    if (root.val == x) {
        root.val = y;
        count--;
    } else if (root.val == y) {
        root.val = x;
        count--;
    }
    recover(root.left, count, x, y);
    recover(root.right, count, x, y);
    

    }

} ```