20240312-算法复习打卡day21||● 530.二叉搜索树的最小绝对差 ● 501.二叉搜索树中的众数 ● 236. 二叉树的最近公共祖先

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

1.中序遍历得到升序数组

class Solution {
private:vector<int> vec;void traversal(TreeNode* root) {if (root == NULL) return;if (root->left) traversal(root->left);vec.push_back(root->val);if (root->right) 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;}
};

2.递归的时候进行最小绝对差的比较

class Solution {
private:int result = INT_MAX;TreeNode* pre = NULL;void traversal(TreeNode* cur) {if (cur == NULL) return;traversal(cur->left);if (pre != NULL) {result = min(result, cur->val - pre->val);}pre = cur;traversal(cur->right);}
public:int getMinimumDifference(TreeNode* root) {traversal(root);return result;}
};

•  501.二叉搜索树中的众数 

1.二叉树情况

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

2.搜索二叉树情况

class Solution {
private:int maxCount = 0;int count = 0;TreeNode* pre = NULL;vector<int> result;void searchBST(TreeNode* cur) {if (cur == NULL) return;searchBST(cur->left);if (pre == NULL) {count = 1;} else if (pre->val == cur->val) {count++;} else {count = 1;}pre = cur;if (count == maxCount) {result.push_back(cur->val);}if (count > maxCount) {maxCount = count;result.clear();result.push_back(cur->val);}searchBST(cur->right);return;}
public:vector<int> findMode(TreeNode* root) {count = 0;maxCount = 0;pre = NULL;result.clear();searchBST(root);return result;}
};

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

1.节点为p或者q或者NULL的时候，返回本身的值到上一个节点去；

2.只有左右都不为NULL（找到了公共祖先），把此时的root节点返回上去（返回上去的只有p,q,NULL,公共祖先这四种情况）

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 left;else if (left == NULL && right != NULL) return right;else {return NULL;}}
};