530.二叉搜索树的最小绝对差
本来想用昨天最后一道题那种解法去做，但是发现有的时候最小值不是两个相邻的节点（错用了二叉搜索树的特性）。中序历遍算出来的。做的时候太马虎了，在主函数里都忘了call travesal，我说怎么min_gap的值不变呢。
class Solution {
public:
vector<int> list;
void travesal(TreeNode* root){
if(root == nullptr){
return ;
}
travesal(root->left);
list.push_back(root->val);
travesal(root->right);
}
int getMinimumDifference(TreeNode* root) {
int min_gap = INT_MAX;
travesal(root);
for(int i=1; i<list.size(); i++){
int cur_min = (list[i]-list[i-1]);
if(min_gap > cur_min){
min_gap = cur_min;
}
}
return min_gap;
}
};
Carl的做法是把计算的过程放到了递归里面。发现自己写起来也不是很容易，而且遇到个问题。不知道怎么比min_gap。
class Solution {
public:
TreeNode* pre = nullptr;
int min_gap = INT_MAX;
void travesal(TreeNode* root){
if(root == nullptr){
return ;
}
travesal(root->left);
int cur_min;
if(pre != nullptr){
cur_min = abs(pre->val - root->val);
}
//min_gap = min(min_gap,cur_min);
cout<<cur_min<<" "<<min_gap<<endl;
if(cur_min < min_gap){
min_gap = cur_min;
}
pre = root;
travesal(root->right);
}
int getMinimumDifference(TreeNode* root) {
travesal(root);
return min_gap;
}
};
知道问题在哪了！
如果把cur_min和min_gap对比放在pre是否是空指针括号之外，那么cur_min的值就不是我们预想中的了，只有pre不是空指针的时候，我们才有cur_min的值。这点太重要了！以后要注意。以下的写法就是对的了。
class Solution {
public:
TreeNode* pre = nullptr;
int min_gap = INT_MAX;
void travesal(TreeNode* root){
if(root == nullptr){
return ;
}
travesal(root->left);
int cur_min;
if(pre != nullptr){
cur_min = abs(pre->val - root->val);
if(cur_min < min_gap){
min_gap = cur_min;
}
}
cout<<cur_min<<" "<<min_gap<<endl;
pre = root;
travesal(root->right);
}
int getMinimumDifference(TreeNode* root) {
travesal(root);
return min_gap;
}
};
501.二叉搜索树中的众数
和上一题差不多。
class Solution {
public:
unordered_map<int,int> u_map;
int max_count = 0;
void travesal(TreeNode* root){
if(root == nullptr){
return ;
}
travesal(root->left);
if(++u_map[root->val] > max_count){
max_count = u_map[root->val];
}
travesal(root->right);
}
vector<int> findMode(TreeNode* root) {
vector<int> res;
travesal(root);
for(auto it= u_map.begin(); it!=u_map.end(); it++){
if(it->second == max_count){
res.push_back(it->first);
}
}
return res;
}
};
Carl的解法是利用了双指针，也是利用了中序遍历。如果pre是空，说明这是第一个节点，count就是1。然后如果cur的节点值等于pre，那count就加一。如果当前的count大于maxcount，那就把res清空再加入当前的值。这样就得到了最多的众数。
这个解法背后的逻辑其实就是中序遍历的时候，一样的数肯定是相邻的，那么pre要么就等于cur，或者不等于cur，不会出现pre不等于当前的cur，但在以后遇到了和之前pre相等的数。就相当于用数组把这个有序的数连起来，然后算maxcount。
236. 二叉树的最近公共祖先
看着b站上Carl题解才把题做出来，理解是理解了。但记忆的不深，还需要再写几遍。尤其是几个condition的处理。
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root==nullptr || root==p || root==q){
return root;
}
TreeNode* left = lowestCommonAncestor(root->left,p,q);
TreeNode* right = lowestCommonAncestor(root->right,p,q);
if(left!=nullptr && right!=nullptr){//当左右两个子节点都找到了对应的，那就return当前的父节点
return root;
}
if(left==nullptr && right!=nullptr){
return right;
}
if(left!=nullptr && right==nullptr){
return left;
}
else{
return nullptr;
}
}
};
