程序员经验分享-hwhale

TypeScript算法题实战——二叉搜索树篇

2023-11-06

二叉搜索树，也叫二叉查找树、二叉排序树，是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值。

注意：二叉搜索树中序遍历的结果是有序的
本系列博文将通过一些力扣算法题目学习TypeScirpt，这篇将以二叉搜索树为主题边学习TypeScipt边实战算法。（部分算法思想参考于程序员Carl:代码随想录）

一、判断二叉搜索树

1.1、题目描述

力扣链接：https://leetcode.cn/problems/validate-binary-search-tree/
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

1.2、题解

本题有一个极容易掉进的陷阱：不能单纯的比较左节点小于中间节点，右节点大于中间节点。

因为，可能存在一种情况就是，虽然对每个节点来说左子节点都小于右子节点，但左子树不一定都小于右子树,如：
在这里插入图片描述
因为二叉搜索树要判断的是左子树的点一定都小于右子树的点。
这一题最直观的方法就是中根遍历，只要遍历出的数组是递增的，则满足二叉搜索树：

function isValidBST(root: TreeNode | null): boolean {
    const traveseArr: number[] = [];
    if(root === null)
        return true;
    else traverse(root);
    function traverse(root: TreeNode | null){
        if(root === null)
            return;
        traverse(root.left);
        traveseArr.push(root.val);
        traverse(root.right);
    }
    for (let i = 0, length = traveseArr.length; i < length - 1; i++) {
        if (traveseArr[i] >= traveseArr[i + 1]) return false;
    }
    return true;
}

二、二叉搜索树中的众数

2.1、题目描述

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

结点左子树中所含节点的值 小于等于 当前节点的值
结点右子树中所含节点的值 大于等于 当前节点的值
左子树和右子树都是二叉搜索树

力扣链接：https://leetcode.cn/problems/find-mode-in-binary-search-tree

2.2、题解

首先使用任意遍历方法将树遍历（前、中、后或者层序），然后将遍历出的数字都存入数组当中。

问题就变成了求一个数组当中的众数，要注意的是这个数组里可能有多个众数，即出现同样次数的数字不止一个，比如1,2,2,2,3,3,3或者1,2,2,3,3,4。

要求众数，我们可以用到哈希Map，算出数组内所有数出现的次数，我们设计一个存储出现次数的哈希Map，遍历一遍：

   for(let i = 0; i < traveseArr.length; i++){
        countMap.set(traveseArr[i], (countMap.get(traveseArr[i]) || 0) + 1);
  }

key表示出现的数字，value表示对应出现的次数，然后找到出现次数最多的key输出就好了。题解：

function findMode(root: TreeNode | null): number[] {
    if (root === null) return [];
    const countMap: Map<number, number> = new Map();
    const traveseArr: number[] = [];
    traverse(root);

    function traverse(root: TreeNode | null){
        if(root === null)
            return;
        traverse(root.left);
        traveseArr.push(root.val);
        traverse(root.right);
    }
    
    for(let i = 0; i < traveseArr.length; i++){
        countMap.set(traveseArr[i], (countMap.get(traveseArr[i]) || 0) + 1);
    }
    const countArr: number[][] = Array.from(countMap);
    countArr.sort((a, b) => {
        return b[1] - a[1];
    })
    const resArr: number[] = [];
    const maxCount: number = countArr[0][1];
    for (let i of countArr) {
        if (i[1] === maxCount) resArr.push(i[0]);
    }
    return resArr;
};

在代码中使用到了， const countArr: number[][] = Array.from(countMap);，可以将countMap（类型为哈希Map）转换成二维数组，数组为一个n行2列数组，第一列为出现的数字，第二列为对应数字出现的次数，这样就可以很好进行操作并得到众数了。

三、求二叉搜索树的最近公共祖先

3.1、题目描述

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

力扣链接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/
在这里插入图片描述

3.2、题解

首先我们做一题普通二叉树的最近公共祖先，可以用递归来做，最近公共祖先有一个特点就是：p和q来自于（1）左子树，（2）右子树，（3）根节点的三者其中之二。

function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
	if(root == null)
        return root;
    if(root == p || root == q)
        return root;
    const left = lowestCommonAncestor(root.left, p, q);
    const right = lowestCommonAncestor(root.right, p, q);
    // 即第一次在该节点的左子树和右子树上分别找到了p 和 q
    if(left !== null && right !== null) return root;
    // 暂时只找到一个
    if(left != null) return left;
    if(right != null) return right;
    // 一个都没找到
    return null;
};

而 求二叉搜索树的最近公共祖先 需要在上一题的基础上，利用一下“二叉搜索树是有序的”这个特点，即从根开始找，如果根节点大于p也大于q，则往左子树找，如果根节点小于q也小于p，则往右子树找，如果不满足同时小于或者大于，那么他就是我们要的最近公共祖先。

function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
	if(root.val > p.val && root.val > q.val){
        return lowestCommonAncestor(root.left, p , q);
    }
    if(root.val < p.val && root.val <q.val){
        return lowestCommonAncestor(root.right, p, q);
    }
    return root;
};

四、二叉搜索树中的插入操作

4.1、题目描述

给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果
力扣链接：https://leetcode.cn/problems/insert-into-a-binary-search-tree

4.2、题解

我们选择不改变树的结构，而是往空结点里面插值，这样做就简单很多，首先判断当前根节点为不为空，若为空则新建一个值为val的结点，返回，若不为空则判断其根节点的值是大于val还是小于val，使用递归的思想，根值大于val就去改左子树，根值小于val就去改右子树。

function insertIntoBST(root: TreeNode | null, val: number): TreeNode | null {
    if(root == null){
        let res: TreeNode =  new TreeNode(val)
        return res;
    }

    if(root.val > val)
        root.left = insertIntoBST(root.left, val);
    else if(root.val < val)
        root.right =insertIntoBST(root.right, val);
    return root;
};

五、删除二叉搜索树中的节点

5.1、题目描述

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

力扣链接：https://leetcode.cn/problems/delete-node-in-a-bst

5.2、题解

一般来说，删除节点可分为两个步骤：首先找到需要删除的节点；如果找到了，删除它。我们主要把算法分成三大块：删除节点的部分、寻找待删除节点的部分，递归返回的部分。

可以利用到二叉搜索树的特性寻找到待删除节点，然后删除节点的方法是把右子树的根节点提上来带他当前节点，然后右子树的最左子节点的左节点接当前左子树。

function deleteNode(root: TreeNode | null, key: number): TreeNode | null {
    if (root === null) return null;
    //删除节点
    if(root.val === key){
        if (root.left === null && root.right === null) return null;
        else if (root.left === null) return root.right;
        else if (root.right === null) return root.left;
        // 把右子树的最左子节点续上
        let curNode: TreeNode = root.right;
        while (curNode.left !== null) {
            curNode = curNode.left;
        }
        curNode.left = root.left;
        return root.right;
    }
    //寻找节点
    else if(root.val < key){
        root.right = deleteNode(root.right, key);
    }
    else if(root.val > key){
        root.left = deleteNode(root.left, key);
    }
    //返回
    return root;
};

六、修剪二叉搜索树

6.1、题目描述

给定一个二叉搜索树，同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树，使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。
题目链接：https://leetcode.cn/problems/trim-a-binary-search-tree/

6.2、题解

如果当前节点值小于low，则切除左子树以及根节点，如果当前节点值大于high，则切除右子树以及根节点，如果当前节点值在low和high的其中，那么就递归到左子树和右子树进行后续操作。

function trimBST(root: TreeNode | null, low: number, high: number): TreeNode | null {
    if (root === null) return null;
    if (root.val < low) {
        return trimBST(root.right, low, high);
    }
    if (root.val > high) {
        return trimBST(root.left, low, high);
    }
    root.left = trimBST(root.left, low, high);
    root.right = trimBST(root.right, low, high);
    return root;
};

七、将有序数组转换为二叉搜索树

7.1、题目描述

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

力扣链接：https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree

7.2、题解

使用二分法加递归的思想，首先要保证高度平衡，且在满足二叉搜索树的前提下，根节点需要选择为该有序数组的中间值，然后左子树即是该值左边的部分，右子树则是其右边的部分，递归继续即可：

function sortedArrayToBST(nums: number[]): TreeNode | null {
    if(nums == null)
        return null;
    else 
        return recur(nums, 0, nums.length - 1);
    function recur(nums:number[], left:number, right:number):TreeNode{
        if(left === right){
            let res:TreeNode = new TreeNode(nums[left]);
            return res;
        }
        if(left > right)
            return null;
        let mid = Math.floor((right + left + 1) / 2);
        let res:TreeNode = new TreeNode(nums[mid]);
        res.left = recur(nums, left, mid - 1);
        res.right = recur(nums, mid + 1 , right);
        return res;
    }
};

八、把二叉搜索树转换为累加树

8.1、题目描述

给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
在这里插入图片描述

力扣链接：https://leetcode.cn/problems/convert-bst-to-greater-tree

8.2、题解

从累加的顺序来看，很简单能看出，累加树的累加顺序是：右=>中=>左，然后设计一个值，在遍历的时候进行累加就好了:

function convertBST(root: TreeNode | null): TreeNode | null {
    let preNum:number = 0;
    recur(root);
    function recur(root: TreeNode | null){
        if (root === null) return;
        recur(root.right);
        root.val += preNum;
        preNum = root.val;
        recur(root.left);
    }
    return root;
};

最后

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

TypeScript算法实战

typescript

算法

数据结构

二叉搜索树

TypeScript算法题实战——二叉搜索树篇 的相关文章

随机推荐

  • 利用webhook实现发送通知到Slack

    概要 最近办公交流应用 Slack在各团队里大行其道 非常火热 今天我们就来说说怎么用他的incoming webhook来做一些同步通知 发送通知给Slack 我们先来看看这种incoming webhook来发送通知的优势 团队成员可以

  • Vulhub Apache HTTPD 换行解析漏洞

    漏洞介绍 漏洞原理 运维人员为了解决 Apache 解析漏洞 会使用 配置 来限制匹配到的最后一个扩展名 这种方式虽然对多个扩展名的解析漏洞进行了防护 但是因为 的正则匹配规则可以将 php n 的扩展名同样可以匹配到 php 的规则 产生

  • Android使用ViewPager实现图片的轮播

    一 概述 在现在的Android项目中 首页图片轮播是随处可见的 今天我们看看如何实现 先看效果图 二 实现 先给大家看看最简单的布局文件

  • 架构之路_深度探索C++对象模型总结

    本文主要参照 深度探索C 对象模型 一书 一 关于对象 C语言中 数据和处理数据的操作 函数 是分开声明的 不支持数据函数之间的关联性 称之为程序性的 procedural 1 1 对象类型 C 中可以通过独立抽象数据类型实现 比如 cla

  • Unity 中场景切换

    Unity游戏开发中 单个Scene解决所有问题似乎不可能 那么多个Scene之间的切换是必然存在 如果仅仅是切换 似乎什么都好说 但是在场景比较大的时候不想让玩家等待加载或者说场景与场景之间想通过一些画面 动画表现出一些让玩家期待的东西

  • 禅道数据库异机访问，远程连接，navicat连接

    禅道数据库异机访问 远程连接 navicat连接 在使用xxj job做执行器时遇到的问题 数据库端口可以在这里修改 可以在这里修改 opt zbox app zentao config my php 禅道数据库官方文档 该链接也有修改数据

  • TP5+Fastadmin+Log日志

    Log 日志 1 引入类 use think Log 2 记录日志 通过Log类的record 方法 记录一条日志 Log record 这是一条普通日志 记录一个错误级别的日志 使用error 方法 Log error 这是一条错误日志

  • 2022届实习+秋招大厂面试经验（后端开发+java）

    个人情况 待补充 求职方向 后端开发 大致情况 20年底在字节实习到21年6月底 转正 21年7月初开始在阿里实习到8月中 转正 随后面试了百度 腾讯和美团 均拿到offer 中间有挂过 被其他部门又捞了 最终选择阿里 我是22年秋季毕业

  • C++函数中返回智能指针的裸指针问题

    注意 如果不是CSDN网站显示本篇文章 请于底部点击 阅读原文 来阅读本篇文章 C 函数中返回智能指针的裸指针问题 要点 原始代码 解决办法 作为一项案例分析下 C 函数中返回智能指针的裸指针问题 要点 不要在函数中返回智能指针的裸指针出去

  • Flutter之MaterialApp使用详解

    如需转载 请尊重作者 注明出处 谢谢配合 22个参数 字段 类型 navigatorKey 导航键 GlobalKey home 主页 Widget routes 路由 Map

  • 非常简单的无闪刷新验证码原理

    非常简单的无闪刷新验证码原理 只有这一段事件触发语句全搞定 nclick this src GifCode asp newDate getTime GifCode asp验证码的图片 事件 nclick this src GifCode a

  • jsp中request经常是的获取参数的方法总结

    我的个人博客开通了 地址 https timewentby com 欢迎访问 下面将获取参数的方法都列出来说一说 request getParameter String name 获取指定name的值 若name有多个相同值则获取第一个va

  • Devoloper warning for package "com..." Failed to post notification on channel "null" see log for det

    使用通知时屏幕显示 这是因为我们使用的是Android O Android 8 0 之前的通知写法 而Android O之后引入了通知通道 Notification channel 重新定义通知内容中的应用程序类别 可以让开发者给予用户更精

  • Kubernetes CKA考试和真题（下）

    前言 之前分享了CKA考试的1 10题 这篇文章继续分享CKA实操考试的最后7到题目 忘了告诉大家 考试的时候可以查看官网资料 监考官是允许这个行为的 但是你不能打开除了k8s官网的其它页面 第11题 启动多容器pod 任务 创建一个名为k

  • 计算巢实现大模型微调——如何发布一个微调服务

    前言 各位看官 最近是否被大模型相关信息刷屏了呢 铺天盖地的大模型预训练 微调等各种关键词是否让你眼花缭乱呢 在如此热度之下 你有没有想过自己亲自动手部署一个大模型执行训练或者微调呢 或许你曾经尝试过却被某个繁琐的步骤劝退了呢 又或者你是模

  • 关于java.lang.NullPointerException: Cannot invoke “org.springframework.data.redis.core.

    java lang NullPointerException Cannot invoke org springframework data redis core RedisTemplate opsForValue because this

  • 机器学习--特征缩放/均值归一化

    特征缩放 feature scaling 其中 特征缩放 feature scaling 大致的思路是这样的 梯度下降算法中 在有多个特征的情况下 如果你能确保这些不同的特征都处在一个相近的范围 这样梯度下降法就能更快地收敛 举个例子来说明

  • Linux中查看所有文件夹及包括文件大小之和

    如果想查看Linux中哪个文件夹最大 可以通过du sh 命令查询哪个文件夹最大 然后进入该文件夹继续执行该命令 直到找出最大的为止 1 Linux中查看所有文件夹和文件大小 这条命令将会计算该文件夹下所有文件大小总和 du sh 执行效果

  • 1、Reading Rasa Source Code —— main

    目录 main main 从 pypi 官方网站上下载 rasa 的最后一个释放版本 截止目前 最新版本为 2 2 1 的源码 解压后 在根目录下 找到 setup py 文件 这是安装引导程序 我们主要关注的是 entry points

  • TypeScript算法题实战——二叉搜索树篇

    二叉搜索树 也叫二叉查找树 二叉排序树 是具有下列性质的二叉树 若它的左子树不空 则左子树上所有结点的值均小于它的根结点的值 若它的右子树不空 则右子树上所有结点的值均大于它的根结点的值 注意 二叉搜索树中序遍历的结果是有序的 本系列博文将

热门标签