【算法day14】二叉树:搜索树的递归问题

ops/2024/12/19 3:11:47/

不好意思呀大家,昨天学校考试耽误了~
来看今天的题目

题目引用


  1. 二叉搜索树的最小绝对差
  2. 二叉搜索树中的众数
  3. 二叉树的最近公共祖先

1.二叉搜索树的最小绝对差


给你一个二叉搜索树的根节点 root ,返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数,其数值等于两值之差的绝对值。

示例 1:
在这里插入图片描述
输入:root = [4,2,6,1,3]
输出:1

我们来看这题,这题其实比前几天做的简单一些,只要理清中间逻辑就好,我们就把二叉树的普通解法和简化的解法都写一下
首先是二叉树的解法,这里我们采用中序遍历,为什么呢,因为题目给的是二叉搜索树,当我们中序遍历搜索树时其实就是在遍历一个有序的数组,求有序数组的差值当然很简单,我们只要使用中序遍历一遍求出相邻节点差值,再用数组记录它,最后进行比对返回结果就可以解决啦。直接看代码

vector<int> vec;void traversal(TreeNode* root){if(root==NULL) return;traversal(root->left);vec.push_back(root->val);traversal(root->right);}int getMinimumDifference(TreeNode* root) {vec.clear();traversal(root);int res=INT_MAX;for(int i=1;i<vec.size();i++){res=min(res,vec[i]-vec[i-1]);}return res;}

那么什么是简化的解法呢,就是在全局变量中定义一个指针用于记录前一个节点,再定义一个result用于记录绝对最小值,在递归过程中直接计算得到就好了。来看代码

private:
int result = INT_MAX;
TreeNode* pre = NULL;
void traversal(TreeNode* cur) {if (cur == NULL) return;traversal(cur->left);   // 左if (pre != NULL){       // 中result = min(result, cur->val - pre->val);}pre = cur; // 记录前一个traversal(cur->right);  // 右
}
public:int getMinimumDifference(TreeNode* root) {traversal(root);return result;}

2.二叉搜索树的众数


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

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

假定 BST 满足如下定义:

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

示例 1:
在这里插入图片描述
输入:root = [1,null,2,2]
输出:[2]

这题应该大家看一眼题目就会联想到之前咱们用过的unordered_map容器,没错,就是它。我们创建一个map,再遍历一遍树,将节点数字作为key,出现次数作为value,再创建一个数组进行由大到小的排序,数组的第一个就是出现最多的众数了。需要注意的是,可能会有出现次数相同的众数,所以我们需要特殊处理一下。
来看代码

void searchBST(TreeNode* root,unordered_map<int,int>& map){if(root==NULL) return;map[root->val]++;searchBST(root->left,map);searchBST(root->right,map);return;}static bool cmp(const pair<int,int>& A,const pair<int,int>& B){return A.second>B.second;}vector<int> findMode(TreeNode* root) {unordered_map<int,int> map;vector<int> res;if(root==NULL) return res;searchBST(root,map);vector<pair<int,int>> vec(map.begin(),map.end());sort(vec.begin(),vec.end(),cmp);res.push_back(vec[0].first);for(int i=1;i<vec.size();i++){if(vec[i].second==vec[0].second) res.push_back(vec[i].first);else break;}return res;}

虽然比较长,但是逻辑很清晰,所以大家可以看一遍以后自己下来再写一遍。但是还有另外一种属于二叉搜索树的写法,我们直接在递归中处理数字出现的次数,并在主函数返回它,因为二叉搜索树的特质,相同数字会在树中相邻且反复出现,所以我们需要一个指针记录前一个节点,当两个节点相等时++,不相等时重新赋值为1,并且更新众数的结果。这样讲有点抽象,直接看代码

private:int maxCount = 0; // 最大频率int count = 0; // 统计频率TreeNode* pre = NULL;vector<int> result;void searchBST(TreeNode* cur) {if (cur == NULL) return ;searchBST(cur->left);       // 左// 中if (pre == NULL) { // 第一个节点count = 1;} else if (pre->val == cur->val) { // 与前一个节点数值相同count++;} else { // 与前一个节点数值不同count = 1;}pre = cur; // 更新上一个节点if (count == maxCount) { // 如果和最大值相同,放进result中result.push_back(cur->val);}if (count > maxCount) { // 如果计数大于最大值频率maxCount = count;   // 更新最大频率result.clear();     // 很关键的一步,不要忘记清空result,之前result里的元素都失效了result.push_back(cur->val);}searchBST(cur->right);      // 右return ;}public:vector<int> findMode(TreeNode* root) {count = 0;maxCount = 0;pre = NULL; // 记录前一个节点result.clear();searchBST(root);return result;}

3.二叉树的最近公共祖先


给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

示例 1:
在这里插入图片描述
输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出:3
解释:节点 5 和节点 1 的最近公共祖先是节点 3 。

我:看题目,要走到最深需要什么遍历(聆听)?
你们:后序遍历! (大声)
对啦,后续遍历。所以这道题目我们就解决一半,只剩最后的逻辑处理。我们用left接受左子树的返回节点,right接受右子树的返回节点。如果左右子树都没有返回那么就返回root自己,left不为空就返回左,right不为空就返回右,都为空就返回空。
来看代码

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (root == q || root == p || root == NULL) return root;TreeNode* left = lowestCommonAncestor(root->left, p, q);TreeNode* right = lowestCommonAncestor(root->right, p, q);if (left != NULL && right != NULL) return root;if (left == NULL && right != NULL) return right;else if (left != NULL && right == NULL) return left;else  { //  (left == NULL && right == NULL)return NULL;}}

总结


今天的题目是对二叉搜索树的简单应用,多多重复,百炼成钢。


http://www.ppmy.cn/ops/143063.html

相关文章

使用C#和OPenCV实现圆形检测

文章目录 霍夫变换使用 OpenCV 和 C# 实现圆形检测霍夫变换 在计算机视觉中,圆形检测是一个常见且有用的任务,特别是在物体识别、图像分析和图形处理等领域。OpenCV 是一个强大的开源计算机视觉库,它提供了许多工具来实现不同的图像处理功能,其中包括圆形检测。本文将介绍如…

Oracle 创建存储过程及调用测试示例

/* select * from NationalDiseases */ /* CREATE OR REPLACE PROCEDURE proc_NationalDiseases ( inp_no_str IN varchar2, v_st_result OUT sys_refcursor ) AS BEGIN DBMS_OUTPUT.PUT_LINE(传入参数&#xff1a;||inp_no_str); open v_st_result for sel…

报错:Method Not Allowed

当报错这个的时候就要注意了&#xff0c;自己的方法是否写对了&#xff01;&#xff01;&#xff01; 就像我的这个因为我的后端是put&#xff0c;所以这也是put&#xff0c;我报错就是因为这写了get&#xff0c;虽然页面是改变了&#xff0c;但是一刷新&#xff0c;就会原形毕…

scp命令

scp&#xff08;Secure Copy Protocol&#xff09;是一种用于在不同主机之间安全传输文件的命令。使用 scp 命令&#xff0c;你可以将文件从本地计算机复制到远程计算机&#xff0c;或者从远程计算机复制到本地计算机。 以下是 scp 命令的基本语法和一些示例&#xff1a; 基本…

【GoF23种设计模式】02_单例模式(Singleton Pattern)

文章目录 前言一、什么是单例模式&#xff1f;二、为什么要用单例模式&#xff1f;三、如何实现单例模式&#xff1f;总结 前言 提示&#xff1a;设计者模式有利于提高开发者的编程效率和代码质量&#xff1a; GoF&#xff08;Gang of Four&#xff0c;四人帮&#xff09;设计…

APP测试中ios和androis的区别,有哪些注意点

一、运行机制不同 IOS采用的是沙盒运行机制&#xff0c;安卓采用的是虚拟机运行机制。 1、沙盒机制&#xff1a; 概念&#xff1a;沙盒是一种安全机制&#xff0c;用于防止不同应用之间互相访问 作用&#xff1a;就是存储数据&#xff0c;每个沙盒就相当于每个每个应用的系…

从〇开始深度学习(1)——PyTorch - Python Deep Learning Neural Network API

从〇开始深度学习(1)——PyTorch - Python Deep Learning Neural Network API 文章目录 从〇开始深度学习(1)——PyTorch - Python Deep Learning Neural Network API<零>写在前面<壹>Part 1: Tensors and Operations1.Section 1: Introducing PyTorch1.1.PyTorch …

vulnhub靶场【shenron】之3

前言 靶机&#xff1a;shenron-3 攻击&#xff1a;kali 都采用虚拟机&#xff0c;网卡为桥接模式 主机发现 使用arp-scan -l或者netdiscover -r 192.168.1.1/24即可 信息收集 使用nmap扫描端口 网站探测 访问网站&#xff0c;发现可能是wordpress&#xff0c;而且经过前…