前言
这里记录一下陈菜菜的刷题记录,主要应对25秋招、春招
个人背景
211CS本+CUHK计算机相关硕,一年车企软件开发经验
代码能力:有待提高
常用语言:C++
系列文章目录
第18天 二叉树 part06
`
文章目录
- 前言
- 系列文章目录
- 第18天 二叉树 part06
- 一、今日任务
- 二、详细布置
- 530.二叉搜索树的最小绝对差
- 提示:
- 样例1:
- 思路
- 实战
- 501.二叉搜索树中的众数
- 提示:
- 样例1:
- 思路
- 实战
- 踩坑
- 236. 二叉树的最近公共祖先
- 提示:
- 样例1:
- 样例2:
- 思路
- 实战
- 总结
一、今日任务
● 530.二叉搜索树的最小绝对差
● 501.二叉搜索树中的众数
● 236. 二叉树的最近公共祖先
二、详细布置
530.二叉搜索树的最小绝对差
题目链接:力扣530
文章讲解:代码随想录
给你一个二叉搜索树的根节点 root ,返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数,其数值等于两值之差的绝对值。
提示:
树中节点的数目范围是 [2, 104]
0 <= Node.val <= 105
样例1:
输入:root = [4,2,6,1,3]
输出:1
思路
这题简单题,遇到二叉排序树,先用中序遍历把它变成有序数组,再做处理。
实战
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:void traversal(TreeNode* root,vector<int>& tree){if(root==NULL)return ;int val=root->val;traversal(root->left,tree);tree.push_back(val);traversal(root->right,tree);}int getMinimumDifference(TreeNode* root) {vector<int> result;int getmin=INT_MAX;traversal(root,result);if(result.size()<2)return 0;for(int i=0;i<result.size()-1;i++){if(getmin>(result[i+1]-result[i]))getmin=result[i+1]-result[i];}return getmin;}
};
501.二叉搜索树中的众数
题目链接:力扣501题链接
文章讲解:图文讲解
给你一个含重复值的二叉搜索树(BST)的根节点 root ,找出并返回 BST 中的所有 众数(即,出现频率最高的元素)。
如果树中有不止一个众数,可以按 任意顺序 返回。
假定 BST 满足如下定义:
结点左子树中所含节点的值 小于等于 当前节点的值
结点右子树中所含节点的值 大于等于 当前节点的值
左子树和右子树都是二叉搜索树
提示:
树中节点的数目在范围 [1, 104] 内
-105 <= Node.val <= 105
样例1:
输入:root = [1,null,2,2]
输出:[2]
思路
这题先变成有序数组,再用map存频率,把众数输出。
实战
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool static cmp (const pair<int, int>& a, const pair<int, int>& b) {return a.second > b.second;
}void traversal(TreeNode* t,vector<int>& res){if(t==NULL)return ;traversal(t->left,res);res.push_back(t->val);traversal(t->right,res);}vector<int> findMode(TreeNode* root) {vector<int> result;vector<int> re;traversal(root,result);//multimap<int,int> mymap;unordered_map<int, int> mymap;for(int i=0;i<result.size();i++)mymap[result[i]]++;vector<pair<int, int>> vec(mymap.begin(), mymap.end());sort(vec.begin(), vec.end(), cmp); re.push_back(vec[0].first);for (int i = 1; i < vec.size(); i++) {if (vec[i].second == vec[0].second) re.push_back(vec[i].first);else break;}return re;}
};
踩坑
mutimap的键值对不能直接比较大小,要重载。
236. 二叉树的最近公共祖先
题目链接:LeetCode236
文章讲解:图文讲解
题目描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
提示:
1 <= s.length <= 104
s 仅由括号 ‘()[]{}’ 组成
样例1:
输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出:3
解释:节点 5 和节点 1 的最近公共祖先是节点 3 。
样例2:
输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出:5
解释:节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
思路
看了题没思路,看题解觉得好巧妙,递归还是牛的,码一下,不太理解的。
实战
class Solution {
public: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;}}
};
总结
今天主要学习了二叉树的一系列操作,今天公共父节点那题比较难,其他还行。
加油,坚持打卡的第17天。