立志重刷代码随想录60天冲冲冲！！——第十八天

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

写递归稍微有一点感觉，双指针解法

class Solution {
public:
    TreeNode* pre = NULL;
    int MinValue = INT_MAX;
    int getMinimumDifference(TreeNode* root) {
        if (root == nullptr) return MinValue;

        int LeftValue = getMinimumDifference(root->left);
        if (pre != NULL && root->val - pre->val < MinValue) {
            MinValue = root->val - pre->val;
        }
        pre = root;
        int RightValue = getMinimumDifference(root->right);
        return MinValue;
    }
};

501.二叉搜索树中的众数

我感觉一般解法更适合我记忆。。。

1、先遍历二叉树，存在map中

2、对map的value进行排序（需要注意，排序函数需要加static）

3、排序完成后输出数组的第一个的key，同时查看后面是否有相同的众数

class Solution {
public:
    /* 一般方法，对于普通二叉树寻找众数 */
    // 先遍历，存在map中
    unordered_map<int,int> umap;
    void searchBST(TreeNode* root) {
        if (root == nullptr) return;
        umap[root->val]++;
        searchBST(root->left);
        searchBST(root->right);
        return;
    }

    // 对map中的value进行排序(必须加static)
    bool static cmp(pair<int,int> a, pair<int,int> b) {
        return a.second > b.second;
    }

    vector<int> findMode(TreeNode* root) {
        vector<int> res;
        searchBST(root); // 遍历
        vector<pair<int,int>> vec(umap.begin(), umap.end()); // 转换为数组
        sort(vec.begin(), vec.end(), cmp); // 数组根据value排序
    
        for (int i = 0; i < vec.size(); i++) {
            if (vec[i].second == vec[0].second) {
                res.push_back(vec[i].first);
            }
        }
        return res;
    }
};

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

后序，向上操作

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == NULL) return root;
        if (root == p || root == q) return root;

        TreeNode* LeftNode = lowestCommonAncestor(root->left, p, q);
        TreeNode* RightNode = lowestCommonAncestor(root->right, p, q);
        if (LeftNode != NULL && RightNode != NULL) return root;
        else if (LeftNode == NULL && RightNode != NULL) return RightNode;
        else if (LeftNode != NULL && RightNode == NULL) return LeftNode;
        else return NULL;
    }
};