530.二叉树的最小绝对差
给你一个二叉搜索树的根节点
root
,返回 树中任意两不同节点值之间的最小差值 。差值是一个正数,其数值等于两值之差的绝对值。
思路:此题与昨天的验证二叉搜索树很像,同样是中序遍历将二叉树节点按照顺序加入到动态数组中,随后遍历动态数组,维护一个相邻的最小差值即可。
class Solution {
public:
void travelRoot(TreeNode* root,vector<int>& res){
if(root==nullptr){
return ;
}
travelRoot(root->left,res);
res.push_back(root->val);
travelRoot(root->right,res);
}
public:
int getMinimumDifference(TreeNode* root) {
vector<int> res;
travelRoot(root,res);
int minNum=INT_MAX;
for(int i=1;i<res.size();i++){
int num=res[i]-res[i-1];
if(num<minNum){
minNum=num;
}
}
return minNum;
}
};
501.二叉搜索树中的众数
给你一个含重复值的二叉搜索树(BST)的根节点 root ,找出并返回 BST 中的所有 众数(即,出现频率最高的元素)。
如果树中有不止一个众数,可以按 任意顺序 返回。
假定 BST 满足如下定义:
结点左子树中所含节点的值 小于等于 当前节点的值
结点右子树中所含节点的值 大于等于 当前节点的值
左子树和右子树都是二叉搜索树
思路:我感觉二叉搜索树的题目好像大多数都可以这么做,就是有关节点值或他们之间的关系之类的,都可以将二叉树的节点的值按照中序遍历,有序的放入数组中。然后在通过这个动态数组来解决题目。易错点:我在主函数放入动态数组中的时候忘记,当出现次数大于当前数的时候要将动态数组置为空,因为直接替换掉了。
class Solution {
public:
void travelRoot(TreeNode* root,vector<int>& res){
if(root==nullptr){
return ;
}
travelRoot(root->left,res);
res.push_back(root->val);
travelRoot(root->right,res);
return ;
}
public:
vector<int> findMode(TreeNode* root) {
vector<int> res;
travelRoot(root,res);
unordered_map<int,int> mp;
for(int i:res){
mp[i]++;
}
vector<int> vec;
int count=0;
for(auto& j:mp){
if(j.second>count){
vec.clear();//*** 因为当前的值比它大所以要清空
vec.push_back(j.first);
count=j.second;
}else if(j.second==count){
vec.push_back(j.first);
}
}
return vec;
}
};
236.二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
思路:首先要理解公共祖先的概念,然后,这道题的思路是递归,深度优先遍历二叉树中的每个节点,当找到qp节点就返回给上一层,(定义两个节点用于存储)然后判断这两个节点是否为空,若不为空代表找到了p或q的值,判断,如果左右都不为空,返回当前的根节点即可,如下图左侧的情况,若左为空右不为空,代表右子树遇到了pq,返回right。如下图右侧,左不为空 右为空同理。
class Solution {
public:
TreeNode* travelRoot(TreeNode* root, TreeNode* p, TreeNode* q){
if(root==nullptr){
return nullptr;
}
if(root==p||root==q){
return root;
}
TreeNode* left=travelRoot(root->left,p,q);//左子树有没有出现q和p
TreeNode* right=travelRoot(root->right,p,q);//右
if(left!=nullptr&&right!=nullptr){//说明左子树或右子树的左右节点存在q和p
return root;
}
if(left==nullptr&&right!=nullptr){
return right;
}
if(left!=nullptr&&right==nullptr){
return left;
}
else return nullptr;
}
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
TreeNode* node=travelRoot(root,p,q);
return node;
}
};
标签:TreeNode,travelRoot,res,day018,二叉树,return,root,节点
From: https://blog.csdn.net/m0_62956971/article/details/140886190