做图素材网站开哪个vip好,seo外链工具有用吗,网页浏览器哪个好,暖暖 视频 在线 观看 高清**530.二叉搜索树的最小绝对差 **
遇到在二叉搜索树上求什么最值#xff0c;求差值之类的#xff0c;都要思考一下二叉搜索树可是有序的#xff0c;要利用好这一特点。
class Solution {
public:void trival(TreeNode* node, vectorint nums) {if (node nul…
**530.二叉搜索树的最小绝对差 **
遇到在二叉搜索树上求什么最值求差值之类的都要思考一下二叉搜索树可是有序的要利用好这一特点。
class Solution {
public:void trival(TreeNode* node, vectorint nums) {if (node nullptr) return ;trival(node-left, nums);nums.push_back(node-val);trival(node-right, nums);}int getMinimumDifference(TreeNode* root) {// 遇到在二叉搜索树上求什么最值求差值之类的// 都要思考一下二叉搜索树可是有序的要利用好这一特点。vectorint nums;trival(root, nums);int result INT_MAX;for (int i 1; i nums.size(); i) {result min(result, nums[i] - nums[i - 1]);}return result;}
};需要领悟一下二叉树遍历上双指针操作优先掌握递归 题目链接/文章讲解https://programmercarl.com/0530.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E7%BB%9D%E5%AF%B9%E5%B7%AE.html 视频讲解https://www.bilibili.com/video/BV1DD4y11779 **501.二叉搜索树中的众数 **
这种方法对普通二叉树和搜索二叉树都行对于递归函数中序和前序都行因为只是统计一下val的频率
class Solution {
public:void trival(TreeNode* node, unordered_mapint, int map,int maxFreq) {if (node nullptr) return ;trival(node-left, map, maxFreq);map[node-val];maxFreq max(maxFreq, map[node-val]);trival(node-right, map, maxFreq);return;}vectorint findMode(TreeNode* root) {unordered_mapint, int map;vectorint result;int maxFreq 0;if (root nullptr) return result;trival(root, map, maxFreq);// for (const auto entry : map) {// if (entry.second maxFreq) {// result.push_back(entry.first);// }// }for (auto it map.begin(); it ! map.end(); it) {if (it-second maxFreq) {result.push_back(it-first);}}return result;}
};和 530差不多双指针思路不过 这里涉及到一个很巧妙的代码技巧。 可以先自己做做看然后看我的视频讲解。 https://programmercarl.com/0501.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E4%BC%97%E6%95%B0.html 视频讲解https://www.bilibili.com/video/BV1fD4y117gp **236. 二叉树的最近公共祖先 **
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {// 确定返回条件// 如果是叶子节点if (root nullptr || root q || root p) {return root;}// 在左子树中寻找p和q的最近公共祖先TreeNode* leftLCA lowestCommonAncestor(root-left, p, q);// 在右子树中寻找p和q的最近公共祖先TreeNode* rightLCA lowestCommonAncestor(root-right, p, q);// 中// 如果左右子树中都分别找到了p和q则当前节点为最近公共祖先节点if (leftLCA rightLCA) {return root;}// 如果只在左子树中找到了p和q则左子树中的最近公共祖先即为最近公共祖先if (leftLCA) {return leftLCA;}// 如果只在右子树中找到了p和q则右子树中的最近公共祖先即为最近公共祖先return rightLCA;}
};本题其实是比较难的可以先看我的视频讲解 https://programmercarl.com/0236.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88.html 视频讲解https://www.bilibili.com/video/BV1jd4y1B7E2
