leetcode 501 二叉搜索树中的众数

前言

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

参考题解：二叉搜索树中的众数-代码随想录

---

提交代码

方法一：遍历一遍二叉树，使用map来统计统计频率，把频率排个序，最后取前面高频的元素的集合。代码见参考题解。

方法二：能否一次遍历，且不使用附加空间，找到众数呢？可以。递归遍历的时候，保存前一个节点的指针。这个思路比较有意思，我实现了下。

class Solution {
private:
    TreeNode* pre;
    int count,max_appr = INT_MIN;
    vector<int> result;
    void inorder_traverse(TreeNode* root){
        if(root == nullptr)
            return;
        
        inorder_traverse(root->left);
        if(pre != nullptr){
            if(root->val == pre->val) // 使用了上一层节节点pre。本层还没给它进行赋值操作
                count++;
            else
                count = 1;
            if(count > max_appr){
                result.clear();
                result.push_back(root->val);
                max_appr = count;
            }else if(count == max_appr){
                result.push_back(root->val);
            }
        }else{ // 最左节点没有pre，预放入
            count = 1;
            result.push_back(root->val);
            max_appr = 1;
        }
        pre = root; // 保存前一个节点。这个遍历在上一层进行了赋值。
        inorder_traverse(root->right);
    }

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