530. 二叉搜索树的最小绝对差
给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。
示例 1：
输入：root = [4,2,6,1,3] 输出：1
示例 2：
输入：root = [1,0,48,null,null,12,49] 输出：1
方法一—递归1
中序遍历得到二叉树的有序数组,然后寻找更新相邻两个数的差值
递归三部曲: 这个中序递归很简单,不再进行阐述.
参考代码1
vector<int> V; int result = INT_MAX; void traversal(TreeNode* node){ if(node==NULL){ return; } traversal(node->left); V.push_back(node->val); traversal(node->right); } //递归法,中序遍历得到二叉树的有序数组.然后判断相邻两个数的差值.. int getMinimumDifference(TreeNode* root) { traversal(root); for(int i = 1;i < V.size();i++){ result = min(result,V[i]-V[i-1]); } return result; }
方法二—递归2
可以边遍历边进行寻找最小绝对差,只需要在中序遍历的时候,保存当前节点的上一个节点,
参考代码2
//递归法2:在递归过程中直接进行求解 int result = INT_MAX; TreeNode* pre; void traversal(TreeNode* node){ if(node==NULL){ return; } traversal(node->left); if(pre!=NULL){//第一个节点不用进行 min处理,因为没有前一个节点 result = min(result,node->val - pre->val) } pre = node; traversal(node->right); } int getMinimumDifference(TreeNode* root) { traversal(root); return result; }
方法三—迭代
目前还不是很懂…
参考代码3
int getMinimumDifference(TreeNode* root) { stack<TreeNode*> st; TreeNode* cur = root; TreeNode* pre = NULL; int result = 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) { // 中 result = min(result, cur->val - pre->val); } pre = cur; cur = cur->right; // 右 } } return result; }
501. 二叉搜索树中的众数
给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。
假定 BST 有如下定义：
结点左子树中所含结点的值小于等于当前结点的值
结点右子树中所含结点的值大于等于当前结点的值
左子树和右子树都是二叉搜索树
示例1
给定 BST [1,null,2,2], 1 \ 2 / 2 返回[2].
提示：如果众数超过1个，不需考虑输出顺序
方法一—普通二叉树
加入本题给的是一颗普通二叉树,那么可以采取如下的做法.
基本思路: 先把这个二叉树遍历了,用map来统计每个数出现的概率,最后按照概率进行排序,取概率最高的几个即可.
算法步骤:
- 遍历整棵树,用map统计,可以使用前/中/后序都可.
unordered_map<int,int> map; void searchBST(TreeNode* cur) { if(cur==NULL) { return; } map[cur->val]++;//统计元素频率 searchBST(cur->left); searchBST(cur->right); }
把统计出来的map数据,按照频率(也就是map中的value)排序.
由于map无法直接通过value进行排序,C++中可以使用map或者multimap对key排序,但就是不可以对value排序.
所以我们可以把map中的数据以pair<int,int>的形式放入到vector中,然后自定义规则进行排序.
//比较函数 --->自定义排序规则 bool cmp(const pair<int,int>& a,const pair<int,int>& b) { return a.second > b.second; } vector<pair<int,int>> vec(map.begin(),map.end());//由于在map中值是无法进行排序的.但我们可以将其放到vector中,自定义规则进行排序. sort(vec.begin(),vec.end(),cmp);
- 取前面的高频元素
由于元素已经按照频率排完了序,所以只需要取前几个中最大的那几个即可.
result.push_back(vec[0].first); for(int i = 1; i < vec.size(); i++) { if(vec[i].second == vec[0].second) { result.push_back(vec[i].first); } else { //因为是按照频率排过序,所以一旦不满足,直接结束. break; } }
参考代码1
//假如是一个普通二叉树 unordered_map<int,int> map; void searchBST(TreeNode* cur) { if(cur==NULL) { return; } map[cur->val]++;//统计元素频率 searchBST(cur->left); searchBST(cur->right); } //比较函数 --->自定义排序规则 bool cmp(const pair<int,int>& a,const pair<int,int>& b) { return a.second > b.second; } vector<int> findMode(TreeNode* root) { vector<int> result; if(root==NULL) { return {}; } searchBST(root); vector<pair<int,int>> vec(map.begin(),map.end());//由于在map中值是无法进行排序的.但我们可以将其放到vector中,自定义规则进行排序. sort(vec.begin(),vec.end(),cmp); result.push_back(vec[0].first); for(int i = 1; i < vec.size(); i++) { if(vec[i].second == vec[0].second) { result.push_back(vec[i].first); } else { //因为是按照频率排过序,所以一旦不满足,直接结束. break; } } return result; }
方法二—二叉搜索树的性质
二叉树的中序遍历是有序的
代码如下:
void searchBST(TreeNode* cur) { if (cur == NULL) return ; searchBST(cur->left); // 左 （处理节点） // 中 searchBST(cur->right); // 右 return ; }
而如何在处理节点时候来获得众数呢?
我们可以使用pre和cur指针,这样每层处理时只需要比较pre==cur是否成立则可判断是否和前一个元素一样,进而可以统计该元素出现的频率.
初始化是pre=NULL,则count就为1了.
if (pre == NULL) { // 第一个节点 count = 1; // 频率为1 } else if (pre->val == cur->val) { // 与前一个节点数值相同 count++; } else { // 与前一个节点数值不同 count = 1; } pre = cur; // 更新上一个节点
但是题目要求的是求最大频率元素的集合,我们该如何做呢?
常规思路:先遍历一遍数组,找出最大频率maxCount,然后再重新遍历一遍数组,把出现频率为maxCount的元素放入到集合.
但是这个题我们可以遍历一遍就能实现目标.
思路:
如果元素频率count等于maxCount,则要把元素放入到集合中(这样肯定不保险了,万一后面出现更大的呢???),
之后判断count 是否大于maxCount.如果是 则不仅要更新maxCount,还要清空结果集(因为之前的结果集都失效了),放入当前元素.
//更新res和maxCount if(count == maxCount) { //因为一旦这次的元素和上一次不同了,count=1,所以每一次count>=maxCount,res都必须要进行更新. res.push_back(cur->val); } else if(count>maxCount) { //清空 res,想res中加入新的元素.更新maxCount. maxCount = count; res.clear(); res.push_back(cur->val); }
参考代码2
int maxCount;//最大频率 int count;//频率 vector<int> res; TreeNode* pre = NULL; void searchBST(TreeNode* cur) { if(cur==NULL) { return; } searchBST(cur->left); //中间节点的处理 if(pre==NULL) { count==1; } else if(cur->val==pre->val) { count++; } else { count = 1; } //更新res和maxCount if(count == maxCount) { //因为一旦这次的元素和上一次不同了,count=1,所以每一次count>=maxCount,res都必须要进行更新. res.push_back(cur->val); } else if(count>maxCount) { //清空 res,想res中加入新的元素.更新maxCount. maxCount = count; res.clear(); res.push_back(cur->val); } pre = cur;//更新上一个节点 searchBST(cur->right); } vector<int> findMode(TreeNode* root) { if(root==NULL) { return {}; } searchBST(root); return res; }
236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 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 。
示例 2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：
输入：root = [1,2], p = 1, q = 2 输出：1
方法一
思路:如果找到一个节点，发现左子树出现结点p，右子树出现节点q，或者 左子树出现结点q，右子树出现节点p，那么该节点就是节点p和q的最近公共祖先。
使用后序遍历,回溯的过程就是从低向上遍历节点,一旦发现符合这个条件的节点,就是最近的公共节点了.
参考代码1
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(root==NULL||root == p || root == q){ return root; } //遍历整棵树 TreeNode* left = lowestCommonAncestor(root->left,p,q); TreeNode* right = lowestCommonAncestor(root->right,p,q); if(left && right){ return root; }else if(!left && right){//如果不再左子树,但在右子树则返回右子树节点. return right; }else if(left && !right){//如果不在右子树,但在左子树则返回左子树节点. return left; } return NULL;//如果都不再,则返回NULL; }
