代码随想录二刷Day21

今日任务

530.二叉搜索树的最小绝对差
501.二叉搜索树中的众数
236.二叉树的最近公共祖先
语言：C++

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

链接：https://leetcode.cn/problems/minimum-absolute-difference-in-bst/
递归

class Solution {
public:vector<int> res;void traversal(TreeNode* cur){if(cur == NULL) return;traversal(cur->left);res.push_back(cur->val);traversal(cur->right);}int getMinimumDifference(TreeNode* root) {traversal(root);int min = INT_MAX;for(int i = 1; i < res.size(); i++){min = min < res[i] - res[i - 1] ? min : res[i] - res[i - 1];}return min;}
};

迭代（非双指针）

class Solution {
public:vector<int> res;int getMinimumDifference(TreeNode* root) {stack<TreeNode*> st;TreeNode* cur = root;while(cur != NULL || !st.empty()){if(cur != NULL){st.push(cur);cur = cur->left;}else{cur = st.top();st.pop();res.push_back(cur->val);cur = cur->right;}}int min = INT_MAX;for(int i = 1; i < res.size(); i++){min = min < res[i] - res[i - 1] ? min : res[i] - res[i - 1];}return min;}
};

迭代（双指针）

class Solution {
public:int res = INT_MAX;int getMinimumDifference(TreeNode* root) {stack<TreeNode*> 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) res = min(res, cur->val - pre->val); //中pre = cur;cur = cur->right; //右}}return res;}
};

501. 二叉搜索树中的众数

链接：https://leetcode.cn/problems/find-mode-in-binary-search-tree/
普通二叉树就用哈希表，然后按照出现次数从大到小排序
递归

class Solution {
public:vector<int> res;int curCount = 1;int maxCount = INT_MIN;TreeNode* pre = NULL;void traversal(TreeNode* cur){if(cur == NULL) return;traversal(cur->left);if(pre && pre->val == cur->val) curCount++;else curCount = 1;pre = cur;if(curCount == maxCount) res.push_back(cur->val);else if(curCount > maxCount){res.clear();maxCount = curCount;res.push_back(cur->val);}traversal(cur->right);}vector<int> findMode(TreeNode* root) {TreeNode* cur = root;traversal(cur);return res;}
};

迭代

class Solution {
public:int maxCount = INT_MIN;int curCount = 1;vector<int> res;vector<int> findMode(TreeNode* root) {if(root->left == NULL && root->right == NULL){res.push_back(root->val);return res;}TreeNode* cur = root;TreeNode* pre = NULL;stack<TreeNode*> st;while(!st.empty() || cur != NULL){// if(pre) cout << pre->val << " ";// else cout << "pre=NULL" << " ";// if(cur) cout << cur->val << endl;// else cout << "cur=NULL" << endl;if(cur != NULL){st.push(cur);cur = cur->left;}else{cur = st.top();st.pop();if(pre && pre->val == cur->val) curCount++;else curCount = 1;if(maxCount == curCount) res.push_back(cur->val);else if(maxCount < curCount){maxCount = curCount;res.clear();res.push_back(cur->val);}pre = cur;cur = cur->right;}}return res;}
};

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

链接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/

class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root == p || root == q || root == NULL) return root;TreeNode* left = lowestCommonAncestor(root->left, p, q); //leftTreeNode* right = lowestCommonAncestor(root->right, p, q); //rightif(left != NULL && right != NULL) return root; //rootif(left == NULL && right != NULL) return right;return left;}
};