【LC刷题】DAY16：530 501 236
文章目录
- 【LC刷题】DAY16：530 501 236
- 530. 二叉搜索树的最小绝对差 [link](https://leetcode.cn/problems/minimum-absolute-difference-in-bst/description/)
- 501.二叉搜索树中的众数
- 236. 二叉树的最近公共祖先 [link](https://leetcode.cn/problems/minimum-absolute-difference-in-bst/description/)
530. 二叉搜索树的最小绝对差 link
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<int> vec;void traverse(TreeNode* root){if(!root){return;}if(root->left) traverse(root->left);vec.push_back(root->val);if(root->right) traverse(root->right);}int getMinimumDifference(TreeNode* root) {vec.clear();traverse(root);int result = INT_MAX;for(int i = 1; i < vec.size(); i++){result = min (result, vec[i] - vec[i - 1]);}return result;}
};
501.二叉搜索树中的众数
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int maxCount = 0;int count = 0;TreeNode* pre = nullptr;vector<int> result;void searchBST(TreeNode* cur){if(cur == nullptr) return;searchBST(cur->left);if(pre == nullptr){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 ;}vector<int> findMode(TreeNode* root) {count = 0;maxCount = 0;pre = nullptr;result.clear();searchBST(root);return result;}};
236. 二叉树的最近公共祖先 link
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root == q || root == p || root == nullptr) return root;TreeNode* left = lowestCommonAncestor(root->left, p, q);TreeNode* right = lowestCommonAncestor(root->right,p ,q);if(left != nullptr && right != nullptr) return root;if(left == nullptr) return right;return left;}
};
