leetcode 501. Find Mode in Binary Search Tree 寻找出现最多次数的元素 + 二叉搜索树BST的中序遍历

- 日理万妓 2022-06-03 00:26 122阅读 0赞

Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST.

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than or equal to the node’s key.  
The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.  
Both the left and right subtrees must also be binary search trees.  
For example:  
Given BST \[1,null,2,2\],  
1  
\\  
2  
/  
2  
return \[2\].

Note: If a tree has more than one mode, you can return them in any order.

Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).

题意很简单，就是寻找出现元素次数最多的元素

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <cmath>
    
    using namespace std;
    
    
    /*
    struct TreeNode
    {
         int val;
         TreeNode *left;
         TreeNode *right;
         TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    */
    
    class Solution
    {
    public:
        vector<int> res;
        map<int, int> mmp;
        vector<int> findMode(TreeNode* root)
        {
            int maxCount = 0;
            getAll(root, maxCount);
            for (auto a : mmp)
            {
                if (a.second == maxCount)
                    res.push_back(a.first);
            }
            return res;
        }
    
        void getAll(TreeNode* root, int& maxCount)
        {
            if (root == NULL)
                return;
            else
            {
                getAll(root->left,maxCount);
    
                if (mmp.find(root->val) == mmp.end())
                    mmp[root->val] = 1;
                else
                    mmp[root->val] += 1;
                maxCount = max(maxCount, mmp[root->val]);
    
                getAll(root->right, maxCount);
            }
        }
    };