LeetCode｜501. Find Mode in Binary Search Tree

题记

时隔若干年后，我又开始刷leetcode了，看看这次会刷多少。

题目

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.

Example 1:

Input: root = [1,null,2,2]
Output: [2]

Example 2:

Input: root = [0]
Output: [0]

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• -105 <= Node.val <= 105

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

思路

第一个想到的思路比较简单，同时也耗时耗空间。
即直接遍历一遍二叉树，然后把每个节点的root->val当作map的索引，出现次数则为map的second值。
遍历之后扫描一遍map中的second值，记录最大的值待用。
再扫描一遍map值，等于最大second的map元素的first值压入vector作为输出。

代码

/**
 * 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 scanTree(TreeNode* root, map<int, int>& m) {
        if (root == NULL)
            return;
        
        if (m.find(root->val) != m.end()) {
            m[root->val]++;
        } else {
            m.insert({root->val, 1});
        }

        scanTree(root->left, m);
        scanTree(root->right, m);

        return;
    }

    vector<int> findMode(TreeNode* root) {
        vector<int> res;
        if (root == NULL)
            return res;
        if (root->left == NULL && root->right == NULL)
        {
            res.push_back(root->val);
            return res;
        }

        map<int, int> m;
        scanTree(root, m);
        int max = 0;
        for (map<int, int>::iterator iter=m.begin(); iter!=m.end(); iter++) {
            if (iter->second > max) {
                max = iter->second;
            }
        }

        for (map<int, int>::iterator iter=m.begin(); iter!=m.end(); iter++) {
            if (iter->second == max) {
                res.push_back(iter->first);
            }
        }

        return res;
    }
};

时间效率和空间占用都有很多可优化的空间。