代码随想录算法训练营第二十一天 | 530.二叉搜索树的最小绝对差、501.二叉搜索树中的众数、236. 二叉树的最近公共祖先

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

题目链接：530.二叉搜索树的最小绝对差

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

文章讲解/视频讲解：https://programmercarl.com/0530.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E7%BB%9D%E5%AF%B9%E5%B7%AE.html

思路

对于一棵二叉搜索树进行中序遍历，可以得到单调递增的序列。因此要想得到二叉搜索树的最小绝对差，可以对该二叉树进行中序遍历，然后判断得到的序列的最小相邻值。

C++实现

// 递归实现
class Solution {
public:
    TreeNode* pre = nullptr;

    int getMinimumDifference(TreeNode* root) {
        int minDistance = numeric_limits<int>::max();
        Traversal(root, minDistance);
        return minDistance;
    }

    void Traversal(TreeNode* node, int& minDistance){
        if(node == nullptr) return;
        Traversal(node->left, minDistance);
        if(pre){
            minDistance = min(minDistance, abs(node->val - pre->val));
        }
        pre = node;
        Traversal(node->right, minDistance);
    }
};
// 迭代实现
class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        TreeNode* pre = nullptr;
        int minDistance = numeric_limits<int>::max();

        stack<TreeNode*> stk;
        TreeNode* cur = root;

        while(!stk.empty() || cur){
            if(cur){
                stk.push(cur);
                cur = cur->left;
            }
            else{
                TreeNode* tmp = stk.top();
                stk.pop();
                if(pre) minDistance = min(minDistance, abs(tmp->val - pre->val));
                pre = tmp;

                cur = tmp->right;
            }
        }

        return minDistance;
    }
};

501.二叉搜索树中的众数

题目链接：501.二叉搜索树中的众数

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

• 结点左子树中所含节点的值 小于等于 当前节点的值
• 结点右子树中所含节点的值 大于等于 当前节点的值
• 左子树和右子树都是二叉搜索树

文章讲解/视频讲解：https://programmercarl.com/0501.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E4%BC%97%E6%95%B0.html

思路

最简单的思路，创建一个哈希表，然后中序遍历二叉搜索树，统计每个数值的出现频率，取最高频率的数值返回。

另外，由于题目中要处理的是二叉搜索树，那么就可以根据二叉搜索树的性质，中序遍历，统计连续数值的最长值，将连续最长的数值返回。

C++实现

// 简单思路
class Solution {
public:
    vector<int> findMode(TreeNode* root) {
        unordered_map<int,int> hashMap;
        stack<TreeNode*> stk;
        TreeNode* cur = root;
        while(!stk.empty() || cur){
            if(cur){
                stk.push(cur);
                cur = cur->left;
            }
            else{
                TreeNode* tmp = stk.top();
                stk.pop();
                hashMap[tmp->val] += 1;
                cur = tmp->right;
            }
        }
        int maxFreq = numeric_limits<int>::min();
        for(const auto& q: hashMap){
            maxFreq = max(maxFreq, q.second);
        }
        vector<int> results;
        for(const auto& q: hashMap){
            if(q.second == maxFreq) results.push_back(q.first);
        }
        return results;
    }
};

// 不利用额外空间的解法
class Solution {
private:
    TreeNode* pre = nullptr;
    int count = 1;
    int maxCount;
    vector<int> results;

    void Traversal(TreeNode* node){
        if(node == nullptr) return;
        Traversal(node->left);
        if(pre){
            if(node->val == pre->val){
                count++;
            }
            else{
                count = 1;
            }
        }
        pre = node;
        if(count > maxCount){
            maxCount = count;
            results.clear();
            results.push_back(node->val);
        }
        else if(count == maxCount){
            results.push_back(node->val);
        }
        Traversal(node->right);
    }
public:
    vector<int> findMode(TreeNode* root) {
        maxCount = 1;
        Traversal(root);
        return results;
    }
};

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

题目链接：236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

文章讲解/视频讲解：https://programmercarl.com/0236.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88.html

思路

对于节点p、q，分别找到从根节点root到p、q的路径，用数组存储两条路径，并将路径反转，然后找到两条路径中交叠的第一个节点，交叠的第一个节点便是两个指定节点的最近公共祖先。

C++实现

class Solution {
public:
    bool findPath(TreeNode* node, int target, vector<TreeNode*>& path){
        if(!node) return false;
        if(node->val == target){
            path.push_back(node);
            return true;
        }
        path.push_back(node);
        bool leftSuccess = findPath(node->left, target, path);
        bool rightSuccess = findPath(node->right, target, path);
        if(leftSuccess || rightSuccess){
            return true;
        }
        path.pop_back();
        return false;
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        vector<TreeNode*> path1, path2;
        findPath(root, p->val, path1);
        findPath(root, q->val, path2);
        reverse(path1.begin(), path1.end());
        reverse(path2.begin(), path2.end());

        for(int i = 0;i<path1.size();i++){
            for(int j = 0;j<path2.size();j++){
                if(path1[i]->val == path2[j]->val){
                    return path1[i];
                }
            }
        }
        return nullptr;
    }
};