常熟建设局网站,宝塔面板安装wordpress,移动网站开发面试题,深圳网站建设公司官网#xff08;四#xff09;二叉搜索树的基础修改构造及属性求解1 二叉搜索树中的搜索递归法迭代法 验证二叉搜索树#xff08;模板题#xff09;递归 数组递归 双指针迭代法 二叉搜索树的最小绝对差递归 数组递归 双指针迭代法 二叉搜索树中的众数求二叉树的众数二叉搜索… 四二叉搜索树的基础修改构造及属性求解1 二叉搜索树中的搜索递归法迭代法 验证二叉搜索树模板题递归 数组递归 双指针迭代法 二叉搜索树的最小绝对差递归 数组递归 双指针迭代法 二叉搜索树中的众数求二叉树的众数二叉搜索树的众数递归法迭代法 二叉搜索树中的搜索
力扣原题链接700.二叉搜索树中的搜索 给定二叉搜索树BST的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在则返回 NULL。 输入root [4,2,7,1,3], val 2 输出[2,1,3]
核心思路
二叉搜索树是一个有序树
若它的左子树不空则左子树上所有结点的值均小于它的根结点的值若它的右子树不空则右子树上所有结点的值均大于它的根结点的值它的左、右子树也分别为二叉搜索树
这就决定了二叉搜索树递归遍历和迭代遍历和普通二叉树都不一样。
递归法
1. 确定递归函数的参数和返回值 递归函数的参数传入的就是根节点和要搜索的数值返回的就是以这个搜索数值所在的节点代码如下
TreeNode* traversal(TreeNode* root, int val)2. 确定终止条件 如果root为空或者找到这个数值了就返回root节点。
if(root NULL || root-val val)return root;3. 确定单层递归的逻辑 因为二叉搜索树的节点是有序的所以可以有方向的去搜索。如果root-val val搜索左子树如果root-val val就搜索右子树最后如果都没有搜索到就返回NULL代码如下
TreeNode* result NULL;
if(val root-val)result traversal(root-left, val);
elseresult traversal(root-right, val);
return result;整体代码如下
class Solution {
public://递归法TreeNode* traversal(TreeNode* root, int val){if(root NULL || root-val val)return root;TreeNode* result NULL;if(val root-val)result traversal(root-left, val);elseresult traversal(root-right, val);return result;}TreeNode* searchBST(TreeNode* root, int val) {return traversal(root,val);}
};因为搜索到了目标节点所以要立即返回这样才符合找到节点就返回的逻辑搜索某一条边如果不加return那么就是遍历整棵树了。
迭代法 因为二叉搜索树的特殊性也就是节点的有序性可以不使用辅助栈或者队列就可以写出迭代法。 对于二叉搜索树不需要回溯的过程因为节点的有序性就帮我们确定了搜索的方向。 例如要搜索元素为3的节点我们不需要搜索其他节点也不需要做回溯查找的路径已经规划好了。 中间节点如果大于3就向左走如果小于3就向右走如图 所以迭代法代码如下
//迭代法
TreeNode* searchBST(TreeNode* root, int val) {while(root ! NULL){if(val root-val)root root-left;else if(val root-val)root root-right;elsereturn root;}return NULL;
}小结 基于二叉搜索树的有序性遍历的时候要充分利用二叉搜索树的特性。 验证二叉搜索树模板题
这是一题解决二叉搜索树中的三种常见思路题
力扣原题链接98. 验证二叉搜索树
给定一个二叉树判断其是否是一个有效的二叉搜索树。
一个二叉搜索树具有如下特征
节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。
示例1
输入root [2,1,3] 输出true
示例2
输入root [5,1,4,null,null,3,6] 输出false 解释根节点的值是 5 但是右子节点的值是 4 。
核心思路
中序遍历下输出的二叉搜索树节点的数值是有序序列。有了这个特性验证二叉搜索树就相当于变成了判断一个序列是不是递增的了。
递归 数组
思路1可以递归中序遍历将二叉搜索树转变成一个数组然后只要比较一下这个数组是否是有序即可注意二叉搜索树中不能有重复元素。
递归遍历把数据存入数组
vectorintresult; //中序遍历 结果数组
//思路1中序遍历 数据值是有序的 中序遍历数据存数组 判断数组是否单增
//递归法
bool traversal(TreeNode* root)
{//假设为空嘛 if(root NULL)return true;traversal(root-left); //左result.push_back(root-val); //中traversal(root-right); //右
}判断数组是否单增来判断二叉树是否为二叉搜索树
bool isValidBST(TreeNode* root)
{traversal(root);//判断数组是否单增for(int i 1; i result.size(); i){if(result[i] result[i-1])return false;}return true;
}以上代码中把二叉树转变为数组来判断是最直观的但其实不用转变成数组可以在递归遍历的过程中直接判断是否有序。
这道题目比较容易陷入两个陷阱
陷阱1
不能单纯的比较左节点小于中间节点右节点大于中间节点就完事了写出了类似这样的代码
if (root-val root-left-val root-val root-right-val)return true;
else return false;我们要比较的是 左子树所有节点小于中间节点右子树所有节点大于中间节点。 所以以上代码的判断逻辑是错误的例如 陷阱2 样例中最小节点 可能是int的最小值如果这样使用最小的int来比较也是不行的此时可以初始化比较元素为longlong的最小值。
递归 双指针
思路2在递归遍历的过程中直接判断是否有序
递归三部曲
1. 确定递归函数返回值以及参数 要定义一个longlong的全局变量用来比较遍历的节点是否有序即上一个节点的值递归函数返回bool类型供上一个节点因此递归函数为
//相当于记录上一节点的数值
long long maxVal LONG_MIN;
bool isValidBST(TreeNode* root) 2. 确定终止条件 遍历到空节点返回假设如果就是空节点那是二叉搜索树因此返回true代码如下
//假设为空嘛
if(root NULL) return true;3. 确定单层递归的逻辑 中序遍历一直更新maxVal一旦发现maxVal root-val就返回false注意元素相同时候也要返回false代码如下
bool left isValidBST(root-left); //左
if(root-val maxVal) //中maxVal root-val;
elsereturn false;
bool right isValidBST(root-right); //右return left right;整体迭代代码如下
long long maxVal LONG_MIN; //相当于记录上一节点的数值
bool isValidBST(TreeNode* root)
{//假设为空嘛 if(root NULL)return true;bool left isValidBST(root-left); //左if(root-val maxVal) //中maxVal root-val;elsereturn false;bool right isValidBST(root-right); //右return left right;}递归优化 那如果后台测试数据有longlong的最小值呢无法再初始化一个更小的值了吧建议避免初始化最小值使用双指针的办法快慢指针首先取到最左面节点数值每次快指针与之前的值做比较即可。
/**************双指针优化****************/
TreeNode* pre NULL;
bool isValidBST2(TreeNode* root)
{//假设为空嘛 if(root NULL)return true;bool left isValidBST(root-left); //左if(pre ! NULL pre-val root-val) //中return false;pre root;bool right isValidBST(root-right); //右return left right;
}迭代法
这是一个二叉搜索树中序遍历的模板需熟记 可以用迭代法模拟二叉树中序遍历且与遍历普通二叉树模板类似迭代法中序遍历稍加改动就可以了变成二叉搜索树迭代模板代码如下:
bool isValidBST3(TreeNode* root)
{stackTreeNode* st;TreeNode* cur root; //当前遍历指针TreeNode* pre NULL; //慢一步的指针while(cur ! NULL || !st.empty()){if(cur ! NULL){st.push(cur);cur cur-left; //左}else{cur st.top(); //中st.pop(); if(pre ! NULL cur-val pre-val)return false;pre cur; //跟新慢指针,保存前一个访问的结点cur cur-right; //右}}return true;
}二叉搜索树的最小绝对差
力扣原题链接530. 二叉搜索树的最小绝对差 给定一个二叉搜索树的根节点 root 返回树中任意两不同节点值之间的最小差值 差值是一个正数其数值等于两值之差的绝对值。
示例
输入 root [4, 2, 6, 1, 3] 输出 1
继续延用上述三种思路
思路1 递归遍历数据到数组后求最小差值思路2 利用双指针在递归遍历时候比较最小差值思路3 利用迭代法与双指针遍历二叉树时比较最小差值
递归 数组
转化为 递归中序遍历到数组求有序数组中两个数的最小差值
思路1程序实现
/****************递归法 数据存入数组******************/
vectorint res;
//中序 递归遍历数据到数组
void traversal(TreeNode* node)
{if(node NULL)return;traversal(node-left); //左res.push_back(node-val); //中traversal(node-right); //右
}
//求解有序数组的最小差值
int getMinimumDifference(TreeNode* root)
{traversal(root);if(res.size() 2)return 0;int minDiff abs(res[1] - res[0]);for(int i 2; i res.size(); i)minDiff min(minDiff, res[i] - res[i-1]);return minDiff;
}递归 双指针
其实在二叉搜素树中序遍历的过程中我们就可以直接计算了需要用一个pre节点记录一下cur节点的前一个节点。
代码如下
/*******************递归双指针法 ***************/
TreeNode* pre NULL;
int minDiff INT_MAX;
void traversal(TreeNode* node)
{if(node NULL)return;traversal(node-left); //左//中if(pre ! NULL)minDiff min(minDiff, node-val - pre-val);pre node; //跟新慢指针traversal(node-right); //右
}int getMinimumDifference(TreeNode* root)
{traversal(root);return minDiff;
}迭代法 可以用迭代法模拟二叉树中序遍历且与遍历普通二叉树模板类似迭代法中序遍历稍加改动就可以了在遍历中加入前一个节点的指针并不断判断更新最小差值即可代码如下:
/****************迭代法***************/
int getMinimumDifference(TreeNode* root)
{ if(root NULL)return 0;stackTreeNode*st;TreeNode* pre NULL;TreeNode* cur root;int minDiff INT_MAX;while(cur ! NULL || !st.empty()){if(cur ! NULL){st.push(cur);cur cur-left; //左}else{cur st.top(); //中st.pop();if(pre ! NULL)minDiff min(minDiff, cur-val - pre-val);pre cur;cur cur-right; //右}}return minDiff;
}总结 遇到在二叉搜索树上求什么最值求差值之类的都要思考一下二叉搜索树可是有序的要利用好这一特点。 同时要学会在递归遍历的过程中如何记录前后两个指针这也是一个小技巧学会了还是很受用的。 二叉搜索树中的众数
力扣原题链接501. 二叉搜索树中的众数
给你一个含重复值的二叉搜索树BST的根节点 root 找出并返回 BST 中的所有 众数即出现频率最高的元素如果树中有不止一个众数可以按 任意顺序 返回。 输入root [1,null,2,2] 输出[2]
如果对于普通的二叉树而言呢
求二叉树的众数
思路: 如果不是二叉搜索树最直观的方法一定是把这个树都遍历了用map统计频率把频率排个序最后取前面高频的元素的集合。
具体步骤如下
1. 节点数据存map 至于用前中后序哪种遍历也不重要因为就是要全遍历一遍这里采用前序遍历代码如下
// mapint, int key:元素value:出现频率
void traversal(TreeNode* node,unordered_mapint, int mp)
{if(node NULL)return;mp[node-val]; //中 统计元素频率traversal(node-left, mp); //左 traversal(node-right, mp); //右return;
}2. 把统计的出来的出现频率即map中的value排个序
C中只能根据map的key进行排序无法对value排序所以要把map转化数组即vector再进行排序当然vector里面放的也是对组 pairint, int类型的数据第一个int为元素第二个int为出现频率。
代码实现如下
//排序仿函数
bool static cmp(const pairint,int a, const pairint, int b)
{return a.second b.second;
}//把map转化为vector其中存放的数据类型是对组
vectorpairint,int vec(resMap.begin(), resMap.end());
sort(vec.begin(), vec.end(), cmp); // 给频率排个序3. 取前面高频的元素
此时数组vector中已经是存放着按照频率排好序的pair那么把前面高频的元素取出来就可以了代码如下
for(int i 0; i vec.size(); i)
{if(vec[i].second vec[0].second) //判断出现频率最大的几个数result.push_back(vec[i].first); //把频率最大的几个数存入结果数组elsebreak;
}整体C代码如下
/*思路1: 遍历树 将数值存入map, 并统计出现的次数根据次数排序返回频率最大的几个数*/
// mapint, int key:元素value:出现频率
void traversal(TreeNode* node,unordered_mapint, int mp)
{if(node NULL)return;mp[node-val]; //中 统计元素频率traversal(node-left, mp); //左 traversal(node-right, mp); //右return;
}
//排序仿函数
bool static cmp(const pairint,int a, const pairint, int b)
{return a.second b.second;
}vectorint findMode(TreeNode* root)
{vectorint result; //结果容器unordered_mapint, int resMap; //存放键值对的mapif(root NULL)return result;traversal(root, resMap);//map 转 对组类型的vectorvectorpairint,int vec(resMap.begin(), resMap.end());sort(vec.begin(), vec.end(), cmp); // 给频率排个序for(int i 0; i vec.size(); i){if(vec[i].second vec[0].second) //判断出现频率最大的几个数result.push_back(vec[i].first); //把频率最大的几个数存入结果数组elsebreak;}return result;
}二叉搜索树的众数
递归法
既然是搜索树它中序遍历就是有序的。
中序遍历代码如下
void searchBST(TreeNode* cur) {if (cur NULL) return ;searchBST(cur-left); // 左处理节点 // 中searchBST(cur-right); // 右return ;
}遍历有序数组的元素出现频率从头遍历相邻两个元素作比较然后就把出现频率最高的元素输出就可以了。 弄一个指针指向前一个节点这样每次cur当前节点才能和pre前一个节点作比较。 而且初始化的时候 pre NULL这样当 pre 为 NULL 时候我们就知道这是比较的第一个元素。
代码如下
if (pre NULL) { // 第一个节点count 1; // 频率为1
} else if (pre-val cur-val) { // 与前一个节点数值相同count;
} else { // 与前一个节点数值不同count 1;
}
pre cur; // 更新上一个节点如何知道最大频率呢 应该是先遍历一遍数组找出最大频率maxCount然后再重新遍历一遍数组把出现频率为maxCount的元素放进集合但这种方式遍历了两遍数组。
如何遍历一遍把频率最大的放到数组里面呢 每次频率最大的数都放进结果集若出现更大的频率的数更新整个结果集清空结果集并把最大频率的数放到结果集
频率 count 等于 maxCount最大频率把这个元素加入到结果集中if (count maxCount) { // 如果和最大值相同放进result中result.push_back(cur-val);
}频率 count 大于 maxCount 的时候不仅要更新 maxCount而且要清空结果集因为结果集之前的元素都失效了if (count maxCount) { // 如果计数大于最大值maxCount count; // 更新最大频率result.clear(); // 很关键的一步不要忘记清空result之前result里的元素都失效了result.push_back(cur-val);
}完整代码如下只需要遍历一遍二叉搜索树就求出了众数的集合
/********思路2 利用二叉搜索树 递归遍历 双指针遍历********/TreeNode* pre NULL;
int maxCnt 0; //最大频率
int cnt 0; //单个元素频率
vectorint res; //结果集
void traversal(TreeNode* node)
{if(node NULL)return;traversal(node-left); //左if(pre NULL) //最初cnt 1;else if(pre-val node-val) //数值相同 累加cnt; else //新数据cnt 1;pre node; //更新旧指针/**********核心细节代码区****************/if(cnt maxCnt) //收获频率最大的数res.push_back(node-val);else if(cnt maxCnt) //更新最大频率{maxCnt cnt;res.clear(); //☆有更长的频率 之前存入的结果都作废res.push_back(node-val); //当前新的长度的数记得存进去}traversal(node-right); //右
}vectorint findMode(TreeNode* root)
{traversal(root);return res;
}迭代法
只要把中序遍历转成迭代中间节点的处理逻辑完全一样直接粘贴代码的即可
/********思路3 迭代法********/
vectorint findMode(TreeNode* root)
{int maxCnt 0; //最大频率int cnt 0; //单个元素频率vectorint res;if(root NULL)return res;stackTreeNode* st;TreeNode* pre NULL;TreeNode* cur root;while(cur ! NULL || !st.empty()){if(cur ! NULL){st.push(cur);cur cur-left; //左}else{cur st.top(); //中st.pop(); if(pre NULL) //最初cnt 1;else if(pre-val cur-val) //数值相同 累加cnt; else //新数据cnt 1;pre cur; //更新旧指针/**********核心细节代码区****************/if(cnt maxCnt) //收获频率最大的数res.push_back(cur-val);else if(cnt maxCnt) //更新最大频率{maxCnt cnt;res.clear(); //☆有更长的频率 之前存入的结果都作废res.push_back(cur-val); //当前新的长度的数记得存进去}cur cur-right; //右}}return res;
}
