厦门网站建设网页设计,wordpress去掉自豪,网站数据维护,云南网站优化排名530.二叉搜索树的最小绝对差
思路一#xff1a;二叉搜索树的中序遍历必为升序数组#xff0c;加入数组后计算相邻两个数差值#xff0c;即可求出最小绝对差
思路二#xff1a;同样的思路#xff0c;中序遍历#xff0c;直接使用指针记录上一个节点#xff0c;同时更新…530.二叉搜索树的最小绝对差
思路一二叉搜索树的中序遍历必为升序数组加入数组后计算相邻两个数差值即可求出最小绝对差
思路二同样的思路中序遍历直接使用指针记录上一个节点同时更新差值
class Solution {
public:int resINT_MAX;TreeNode*prenullptr;void judge(TreeNode*root){if(rootnullptr) return;judge(root-left);if(pre!nullptr)resmin(res,root-val-pre-val);preroot;judge(root-right);}int getMinimumDifference(TreeNode* root) {//思路二双指针递归中序遍历计算两节点之间差值judge(root);return res;}
};
501.二叉搜索树中的众数
思路一使用map和vector遍历二叉搜索树用map记录元素出现的次数一次遍历map求出最大次数二次遍历map求出等于最大次数的值加入到vector中思路二使用指针记录pre前一个元素当pre元素和当前cur元素相等时更新count值当pre元素和当前cur元素不等时使用count更新最大次数值maxNum
当count值大于maxNum时清空数组把新的元素加入数组
当count值等于maxNum时把该元素加入数组
236.二叉树的最近公共祖先
思路一第一次遍历二叉树使用左0右1来记录p和q的路径然后找出两个路径的相同值再使用该相同值去遍历二叉树最后遍历到的值即为最近公共祖先
思路二自底向上后序遍历考虑两个指定值的分布情况使用两个指针保存两个指定值找到直接返回找不到返回nullptr
class Solution {
public:TreeNode*judge(TreeNode*root,TreeNode*p,TreeNode*q){if(rootnullptr) return root; if(rootp || rootq) return root;//遍历到值时直接返回TreeNode*leftjudge(root-left,p,q);TreeNode*rightjudge(root-right,p,q);if(left!nullptr right!nullptr) return root;//指定值分布再两侧if(right!nullptr) return right;//指定值分布在右侧if(left!nullptr) return left;//指定值分布在左侧return nullptr;//重点左右都不存在需返回nullptr}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {//后序遍历return judge(root,p,q);}
};
