持续创造，加快生长！这是我参加「日新方案 10 月更文应战」的第5天，点击查看活动概况

恢复二叉查找树

标题

给你二叉查找树的根节点 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 使二叉查找树有用。

处理思路

根据题意可知，是二叉查找树，这便是意味着节点之间是有次序关系的。 假如咱们把整棵树都 遍历 一遍，将遍历的结果保存下来，比如放到一个数组中。 那么这个数组应该是有序的。

既然是有序的那就好办了，咱们将这个有序的数组遍历一遍。 假如数组是完全有序的，那么直接返回就能够了。 否则，咱们找到次序不一致的两个下标i和j，将arr[i].val和arr[j].val的值交换一下即可。

代码完成

/**
 * 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 List<TreeNode> list;
    public void recoverTree(TreeNode root) {
        list = new ArrayList();
        inOrder(root);
        TreeNode x = null;
        TreeNode y = null;
        for (int i = 0; i < list.size() - 1; i++) {
            if (list.get(i).val > list.get(i+1).val){
                y = list.get(i+1);
                if (x == null) {
                    x = list.get(i);
                }
            }
        }
        if (x != null && y != null) {
            int tmp = x.val;
            x.val = y.val;
            y.val = tmp;
        }
    }
    public void inOrder(TreeNode root) {
        if (root == null) return;
        inOrder(root.left);
        list.add(root);
        inOrder(root.right); 
    }
}

复杂度分析

  • 时刻复杂度：O(N)，其间 N 为二叉查找树的节点数。中序遍历需求 O(N) 的时刻，判别两个交流节点在最好的情况下是 O(1)，在最坏的情况下是 O(N)，因此总时刻复杂度为 O(N)。

  • 空间复杂度：O(N)。咱们需求用 数组存储树的中序遍历列表

验证二叉查找树

标题

给你一个二叉树的根节点 root ，判别其是否是一个有用的二叉查找树。

有用 二叉查找树定义如下：

  • 节点的左子树只包括 小于 当时节点的数。
  • 节点的右子树只包括 大于 当时节点的数。
  • 所有左子树和右子树自身有必要也是二叉查找树。

示例1：

验证与恢复二叉搜索树

示例2：

验证与恢复二叉搜索树

解题思路

咱们知道二叉查找树的特性便是，中序遍历后得到的是一个有序的数组，所以咱们能够经过在中序遍历的时候查看当时节点的值是否大于前一个中序遍历的值，假如均大于阐明这个序列是升序的，整棵树是二叉查找树，否则不是。

代码完成

/**
 * 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 long pre = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (!isValidBST(root.left)){
            return false;
        }
        if (root.val <= pre) {
            return false;
        }
        pre = root.val;
        return isValidBST(root.right);
    }
}

复杂度分析

  • 时刻复杂度 : O(n)，其间 n 为二叉树的节点个数。二叉树的每个节点最多被拜访一次，因此时刻复杂度为 O(n)。

  • 空间复杂度 : O(n)，其间 n 为二叉树的节点个数。栈最多存储 n 个节点，因此需求额外的 O(n) 的空间。

我是杰少，假如您觉的我写的不错，那请给我 点赞+谈论+收藏 后再走哦！

往期文章：

  • 运用 Google Breakpad 来助力处理程序溃散
  • UE4 多人游戏服务器探索
  • 运用虚幻引擎主动化东西完成主动化部署
  • 如安在 UE4 中制作一扇主动敞开的大门
  • 如安在 UE4 中用代码去操控人物移动
  • 怎么给 UE4 场景增加游戏人物
  • UE4：Android 渠道开发实践攻略
  • UE4 开发避坑攻略（持续更新）
  • 新年开工啦，放个小焰火庆祝一下
  • 聊聊与苹果审核员的爱恨情仇(下)
  • 聊聊与苹果审核员的爱恨情仇(上)
  • 一名一般东西人的 2021 | 2021年终总结
  • 二叉树刷题总结：二叉查找树的特点
  • 二叉树总结：二叉树的特点
  • 二叉树总结：二叉树的修改与结构
  • StoreKit2 有这么香？嗯，我试过了，真香
  • 看完这篇文章，再也不怕面试官问我怎么结构二叉树啦！
  • 那帮做游戏的又想让我们氪金，太坏了！
  • 手把手带你撸一个网易云音乐主页 | 适配篇
  • 手把手带你撸一个网易云音乐主页（三）
  • 手把手带你撸一个网易云音乐主页（二）
  • 手把手带你撸一个网易云音乐主页（一）
  • 代码要写注释吗？写你就输了
  • Codable发布这么久我就不学，摸鱼爽歪歪，哎~便是玩儿
  • iOS 高雅的处理网络数据，你真的会吗？不如看看这篇
  • UICollectionView 自定义布局！看这篇就够了

请你喝杯 ☕️ 点赞 + 重视哦～

  1. 阅读完记得给我点个赞哦，有 有动力
  2. 重视公众号— HelloWorld杰少，第一时刻推送新姿态

最后，创造不易，假如对我们有所协助，期望我们点赞支持，有什么问题也能够在谈论区里讨论～**