刷题笔记day21

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

文章讲解：代码随想录
是否自己做出来通过全部用例：是

遇到的困难/犯的错误

if (pre != NULL) {
    int dif = abs(pre->val - node->val);
    if (dif < mindif) {
        mindif = dif; 
    }
}
pre = node;

这里的pre要放在if外面，我试图把它放在里面导致pre一直是NULL，永远进不去if条件。

自己写的代码

class Solution {
public:
    TreeNode* pre = NULL;
    int mindif = INT_MAX;
    void getmindif(TreeNode* node) {
        if (!node) return;
        getmindif(node->left);
        if (pre != NULL) {
            int dif = abs(pre->val - node->val);
            if (dif < mindif) {
                mindif = dif; 
            }
        }
        pre = node;
        getmindif(node->right);
    }
    int getMinimumDifference(TreeNode* root) {
        getmindif(root);
        return mindif;
    }
};

看了题解后的收获

遇到在二叉搜索树上求什么最值，求差值之类的，都要思考一下二叉搜索树可是有序的，要利用好这一特点。

501.二叉搜索树中的众数

文章讲解：代码随想录
是否自己做出来通过全部用例：

遇到的困难/犯的错误

最暴力的，中序遍历，用map存储，排序后输出。
递归相对难理解。

自己写的代码

看了题解后写的代码：

class Solution {
public:
    int maxcounts = 0;
    vector<int> maxoccurvals;
    int counts = 1;
    TreeNode* pre = NULL;
    void findmaxoccurval(TreeNode* node) {
        if (!node) return;
        findmaxoccurval(node->left); // 左
        if (pre == NULL) { // 第一个节点
            counts = 1;
        }
        else if (node->val == pre->val) {
            ++counts;
        }
        else counts = 1;
        pre = node;
        if (counts == maxcounts) {
            maxoccurvals.push_back(node->val);
        }
        if (counts > maxcounts) {
            maxoccurvals.clear();
            maxcounts = counts;
            maxoccurvals.push_back(node->val);
        }
        
        findmaxoccurval(node->right); //右
        return;
    }
    vector<int> findMode(TreeNode* root) {
        findmaxoccurval(root);
        return maxoccurvals;
    }
};

看了题解后的收获

普通二叉树和二叉搜索树还是有差别的。
二叉搜索树只能全部遍历，搜索二叉树可以用双指针法。

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

文章讲解：代码随想录
是否自己做出来通过全部用例：否

遇到的困难/犯的错误

判断公共节点的条件（终止条件）没有理清楚。

自己写的代码

看了题解后写的代码：
class Solution {
public:
TreeNode* getlowestCommonAncestor(TreeNode* node, TreeNode* p, TreeNode* q) {
if (!node) return node;
if (p == node || q == node) return node;
TreeNode* left = getlowestCommonAncestor(node->left, p, q);
TreeNode* right = getlowestCommonAncestor(node->right, p, q);
if (left != NULL && right != NULL) return node;
else if (left != NULL && right == NULL) return left;
else if (left == NULL && right != NULL) return right;
else return NULL;
return NULL;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
return getlowestCommonAncestor(root, p, q);
}
};

看了题解后的收获

求最小公共祖先，需要从底向上遍历，那么二叉树，只能通过后序遍历（即：回溯）实现从底向上的遍历方式。
在回溯的过程中，必然要遍历整棵二叉树，即使已经找到结果了，依然要把其他节点遍历完，因为要使用递归函数的返回值（也就是代码中的left和right）做逻辑判断。
要理解如果返回值left为空，right不为空为什么要返回right，为什么可以用返回right传给上一层结果。