代码随想录-训练营-day16

530. 二叉搜索树的最小绝对差 - 力扣（LeetCode）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int res=INT_MAX;
    TreeNode* prenode=nullptr;
    void inorder(TreeNode* node){
        if(!node)return;
        inorder(node->left);
        if(prenode){
            res=min(res,abs(prenode->val-node->val));
        }
        prenode=node;
        inorder(node->right);
    }
    int getMinimumDifference(TreeNode* root) {
        inorder(root);
        return res;
    }
};

我们要充分利用好二叉搜索树的性质，因为我们都知道这种二叉树的任一节点的左子树节点一定比当前节点小，右子树节点一定比当前子树节点大。我们如果选择采取中序遍历的话，就可以实现一个从小到大的遍历效果。我们去记录遍历过的节点，并且检测到当前节点存在的话就进行最小差值的更新。

501. 二叉搜索树中的众数 - 力扣（LeetCode）

我们要去找二叉搜索树的出现频率最高的数。

我们首先想到的就是遍历二叉树所有节点，记录所有节点值出现的频率，再根据频率来排序即可。但这个做法的难点在于我们C++中的哈希表如map并没有根据值来进行排序的做法，所以我们需要将map转换为vector<pair<int,int>>来可以排序。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void inorderTravel(TreeNode* node,unordered_map<int,int>& mp){
        if(!node)return;
        inorderTravel(node->left,mp);
        mp[node->val]++;
        inorderTravel(node->right,mp);
        return;
    }
    bool static cmp(const pair<int,int>& a,const pair<int,int>& b){
        return a.second>b.second;
    }
    vector<int> findMode(TreeNode* root) {
        vector<int> res;
        unordered_map<int,int> mp;
        if(!root)return res;
        inorderTravel(root,mp);
        vector<pair<int,int>> tem(mp.begin(),mp.end());
        sort(tem.begin(),tem.end(),cmp);
        res.push_back(tem[0].first);
        for(int i=1;i<tem.size();++i){
            if(tem[0].second==tem[i].second)res.push_back(tem[i].first);
            else break;
        }
        return res;
    }
};

这种是二叉树通用的寻找众数的方法，通用性强但是没有充分利用上我们的二叉搜索树的性质。

class Solution {
private:
    int maxCount = 0, currentCount = 0;
    vector<int> modes;
    TreeNode* pre = nullptr;
    void inorderTravel(TreeNode* node) {
        if (!node) return;
        inorderTravel(node->left);
        if (pre != nullptr) {
            if (pre->val == node->val) {
                currentCount++;
            } else {
                currentCount = 1;
            }
        } else {
            currentCount = 1; 
        }
        if (currentCount > maxCount) {
            maxCount = currentCount;
            modes.clear(); 
            modes.push_back(node->val);
        } else if (currentCount == maxCount) {
            modes.push_back(node->val);
        }
        pre = node;
        inorderTravel(node->right);
    }

public:
    vector<int> findMode(TreeNode* root) {
        inorderTravel(root);
        return modes;
    }
};

利用我们的二叉搜索树，我们的中序遍历就变成了一个有序遍历。我们在这个过程中不断地维护出现过的值出现的频率并进行比较即可。

236. 二叉树的最近公共祖先 - 力扣（LeetCode）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==p||root==q||!root)return root;
        TreeNode* left=lowestCommonAncestor(root->left,p,q);
        TreeNode* right=lowestCommonAncestor(root->right,p,q);
        if(left&&right)return root;
        if(left)return left;
        else return right;
    }
};

我们采取遍历的方式去根节点的左子树和右子树中找到我们需要找寻公共祖先的两个节点，如果都找到了就返回（利用遍历的本质是栈）。