【Java - L - 0099】h - 恢复二叉搜索树

题目描述

二叉搜索树中的两个节点被错误地交换。
请在不改变其结构的情况下，恢复这棵树。

实现

class Solution {
    // BST 中序有序
    public void recoverTree(TreeNode root) {
        List<TreeNode> list = new ArrayList<>();
        // 中序遍历
        inorder(root, list);
        // 找到相邻不等为错误节点
        int[] nums = swapNodes(list);
        // 交换两个无序节点
        recover(root, 2, nums[0], nums[1]);
    }

    public void inorder(TreeNode root, List<TreeNode> list) {
        if (root == null) return;
        inorder(root.left, list);
        list.add(root);
        inorder(root.right, list);
    }

    //[1,2,3,4,5,6,7]。如果我们交换两个不相邻的数字，例如 2 和 6，原序列变成了 
    //a=[1,6,3,4,5,2,7]，那么显然序列中有两个位置不满足i<a(i+1)，
    // 体现为 6>3，5>2(两个位置)，如果2，3相邻交换则一个节点
    public int[] swapNodes(List<TreeNode> list) {
        int x = -1, y = -1;
        for (int i = 0; i < list.size() - 1; ++i) {
            if (list.get(i + 1).val < list.get(i).val) {
                y = list.get(i + 1).val;
                if (x == -1) {
                    x = list.get(i).val;
                } else {
                    break;
                }
            }
        }
        return new int[]{x, y};
    }

    public void recover(TreeNode root, int count, int x, int y) {
        if (root != null) {
            if (root.val == x || root.val == y) {
                root.val = root.val == x ? y : x;
                if (--count == 0) {
                    return;
                }
            }
            recover(root.right, count, x, y);
            recover(root.left, count, x, y);
        }
    }
}