代码随想录算法训练营第二十一天打卡 | 530.二叉搜索树的最小绝对差、501.二叉搜索树中的众数、236. 二叉树的最近公共祖先

打卡第21天，继续二叉树，前几天终于补完了，感觉难度上来了。

今日任务

• 530.二叉搜索树的最小绝对差
• 501.二叉搜索树中的众数
• 236. 二叉树的最近公共祖先

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

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。

我的题解

突然有了这个想法，左子树的最右，右子树的最左的值是跟目前这个结点的值最接近的，差值也是最小，然后递归遍历左右子树，比较四个值哪个最小。

class Solution {
public:int getMinimumDifference(TreeNode* root) {// 找到本结点左边最大的值，就是值最接近本结点的值TreeNode *cur1 = root->left;while(cur1 != NULL && cur1->right != NULL) {cur1 = cur1->right;}int num1 = INT_MAX;if(cur1 != NULL) num1 = root->val - cur1->val;// 找到本结点右边最小的值TreeNode *cur2 = root->right;while(cur2 != NULL && cur2->left != NULL) {cur2 = cur2->left;}int num2 = INT_MAX;if(cur2 != NULL) num2 = cur2->val - root->val;int l = INT_MAX, r = INT_MAX;// 左右递归if(root->left) l = getMinimumDifference(root->left);if(root->right) r = getMinimumDifference(root->right);return min(min(num1, num2), min(l, r));}
};

代码随想录

利用中序遍历所有结点，得到中序遍历的结点值数组，统计更新 节点值之间的最小差值

class Solution {
private:
vector<int> vec;
void traversal(TreeNode* root) {if (root == NULL) return;traversal(root->left);vec.push_back(root->val); // 将二叉搜索树转换为有序数组traversal(root->right);
}
public:int getMinimumDifference(TreeNode* root) {vec.clear();traversal(root);if (vec.size() < 2) return 0;int result = INT_MAX;for (int i = 1; i < vec.size(); i++) { // 统计有序数组的最小差值result = min(result, vec[i] - vec[i-1]);}return result;}
};

中序遍历递归，保存前一个结点，然后跟目前的结点的值进行计算比较。

class Solution {
public:TreeNode * pre = NULL;int res =INT_MAX;void tarversal(TreeNode* root) {if(root == NULL) return ;tarversal(root->left); //左// 中if(pre != NULL) {res = min(res, root->val - pre->val);}pre = root;tarversal(root->right); //右}int getMinimumDifference(TreeNode* root) {tarversal(root);return res;}
};

501.二叉搜索树中的众数

给你一个含重复值的二叉搜索树（BST）的根节点 root，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
如果树中有不止一个众数，可以按 任意顺序 返回。
假定 BST 满足如下定义：

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

代码随想录

普通二叉树做法

用unordered_map 统计出各结点值的个数，然后排序，找到频率最高的。

class Solution {
public:unordered_map<int, int> cnt;vector<int> res;void tarversal(TreeNode* root) {if(root == NULL) return ;tarversal(root->left);cnt[root->val]++;tarversal(root->right);}bool static cmp(const pair<int, int> &a, const pair<int, int> &b) {return a.second > b.second;}vector<int> findMode(TreeNode* root) {if(root == NULL) return res;tarversal(root);vector<pair<int, int>> vec(cnt.begin(), cnt.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;}
};

搜索二叉树做法

搜索二叉树的中序遍历，会得到一个单调不递减的数组。
当发现当前结点跟前一个结点数值相同，该结点的频率值更新，当发现目前结点的频率值大于最大频率值，更新最大频率值，更新结果集res，当发现目前结点的频率值等于最大频率值，更新结果集。

class Solution {
public:int maxcnt = 0; //最大值频率值int cnt = 0; // 目前结点的频率值vector<int> res;TreeNode* pre = NULL;void tarversal(TreeNode* root) {if(root == NULL) return ;tarversal(root->left);if(pre == NULL) { // 第一个结点cnt = 1;} else if(pre->val == root->val){//与前面的结点相同cnt++;} else {//与前面结点不相同cnt = 1;}pre = root;if(cnt == maxcnt) {//如果和最大值相同，收集到结果res.push_back(root->val);}if(cnt > maxcnt) {//如果计数大于最大值maxcnt = cnt; //更新最大值res.clear(); //更新结果集res.push_back(root->val);}tarversal(root->right);}vector<int> findMode(TreeNode* root) {tarversal(root);return res;}
};

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

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

代码随想录

class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root == NULL) return NULL;if(root == p || root == q) return root;TreeNode *lNode = lowestCommonAncestor(root->left, p, q); // 左 TreeNode *rNode = lowestCommonAncestor(root->right, p, q); // 右// 中if(lNode && rNode) return root;if(lNode && !rNode) return lNode;if(!lNode && rNode) return rNode;return NULL;}
};