[LeetCode] 501. Find Mode in Binary Search Tree

https://leetcode.com/problems/find-mode-in-binary-search-tree/description/

Find Mode in Binary Search Tree - LeetCode

leetcode - Find Mode in Binary Search Tree

문제 유형 : 그래프, 트리, 해시

문제 난이도 : Easy

 

문제

Given the root of a binary search tree (BST) with duplicates, return all the mode(s) (i.e., the most frequently occurred element) in it.

If the tree has more than one mode, return them in any order.

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.

중복 값이 있는 이진 탐색트리의 루트가 주어진다. 모든 mode(s)를 반환하라.

mode는 most frequently occured element, 가장 많이 등장한 요소라는 뜻입니다.

 

풀이

트리를 완전히 순환해야 합니다.

순환을 하는 과정에서 unordered_map에 각 요소별 개수를 저장하면서, 최고의 개수도 찾아냅니다.

 

최고의 개수를 가진 노드를 찾아냅니다.

 

코드

C++

class Solution {
public:
    void traversal(TreeNode* start, vector<int>& result) {
        queue<TreeNode*> q;
        q.push(start);
        result.push_back(start -> val);

        while(!q.empty()) {
            auto curr = q.front();
            q.pop();

            if(curr -> left !=nullptr) {
                q.push(curr -> left);
                result.push_back(curr -> left -> val);
            }

            if(curr -> right !=nullptr) {
                q.push(curr -> right);
                result.push_back(curr -> right -> val);
            }
        }
    }
    vector<int> findMode(TreeNode* root) {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);

        vector<int> vals;
        traversal(root, vals);
        unordered_map<int, int> freq;
        int maxcnt = 0;
        
        for (int val : vals) {
            freq[val]++;
            maxcnt = max(maxcnt, freq[val]);
        }
        
        vector<int> result;
        for (const auto& pair : freq) {
            if (pair.second == maxcnt) {
                result.push_back(pair.first);
            }
        }
        
        return result;
    }
};