• 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);
        }
    
    
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92

    解题思路

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

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

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

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

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

    在这里插入图片描述
    将7和4交换即可。

  • 相关阅读:
    通过HatchBush对象的()属性可设置HatchBush对象的阴影样式。
    接口自动化测试方案模版。希望可以帮到你
    【 背包九讲——完全背包问题】
    学习基因富集工具DAVID(2)
    数据结构二叉树前序遍历递归和非递归算法
    Python爬虫——BS4解析方式简介
    【Linux操作系统】:基本指令
    zip()并行迭代多个序列
    【用unity实现100个游戏之16】Unity程序化生成随机2D地牢游戏2(附项目源码)
    Linux中如何禁止普通用户使用su命令
  • 原文地址:https://blog.csdn.net/weixin_38019299/article/details/125902423