leetcode-99.恢复二叉搜索树

题目

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

示例 1：

输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 的左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
示例 2：

输入：root = [3,1,4,null,null,2]
输出：[2,1,4,null,null,3]
解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。

提示：

树上节点的数目在范围 [2, 1000] 内
-231 <= Node.val <= 231 - 1

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/recover-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

package org.lht.boot.lang.算法.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * Description: https://leetcode.cn/problems/recover-binary-search-tree/
 *
 * @Author lht
 * @Date 2022/7/13 21:00
 **/
public class L99恢复二叉搜索树 {


    public static void main(String[] args) {
        TreeNode root = new TreeNode();
        //..定义参数
        recoverTree(root);
    }

    /**
     * 转换
     * @param root
     */
    public static void recoverTree(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        inorder(root, list);
        int[] index = findIndex(list);
        recoverTree(root, 2, index[0], index[1]);

    }

    /**
     * 根据中序遍历的结果，找到那两个被交换了的节点值。
     * @param nums
     * @return
     */
    public static int[] findIndex(List<Integer> nums) {
        int preIndex = -1;
        int nextIndex = -1;
        for (int i = 0; i < nums.size() - 1; i++) {
            if (nums.get(i) > nums.get(i + 1)) {
                preIndex = i + 1;
                if (nextIndex == -1) {
                    nextIndex = i;
                } else {
                    break;
                }
            }
        }
        int x = nums.get(preIndex), y = nums.get(nextIndex);
        return new int[]{x, y};
    }


    /**
     * 将两个找到的交换了的节点，进行交换过来
     * @param root
     * @param count
     * @param x
     * @param y
     */
    public static void recoverTree(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;
                }
            }
            recoverTree(root.left, count, x, y);
            recoverTree(root.right, count, x, y);
        }
    }

    /**
     * 中序遍历
     *
     * @param root
     * @param nums
     */
    public static void inorder(TreeNode root, List<Integer> nums) {
        if (root == null) {
            return;
        }
        inorder(root.left, nums);
        nums.add(root.val);
        inorder(root.right, nums);
    }


}

解题思路

这个题其实很简单，有几个思路

第一，利用中序遍历的结果为有序的。

第二，二叉搜索树中的两个节点被交换了，树的结构没有变

第三，并且有且只有两个节点被交换了，因此找到两个被交换的节点即可。

第四，交换节点，不用操作树结果，因此采用任何一种遍历即可。

将7和4交换即可。