501.Find Mode in Binary Tree

501.Find Mode in Binary Search Tree

难度:Easy

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)

适应于任何树的方法，直接遍历法。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
unordered_map<int,int>all;
void traversal(TreeNode* root)
{
    if(!root) return;
    all[root->val]++;
    traversal(root->left);
    traversal(root->right);
}
public:
    vector<int> findMode(TreeNode* root) {
        vector<int>res;
        if(!root) return res;
        traversal(root);
        int count=0;
        for(auto& a: all)
        {
            count = max(count, a.second);
        }
        for(auto& a:all)
            if(a.second == count) res.push_back(a.first);
        return res;
    }
};

执行用时 :52 ms, 在所有 C++ 提交中击败了22.86%的用户 内存消耗 :27.1 MB, 在所有 C++ 提交中击败了12.78%的用户

考虑到是BST，可以充分利用其已经排好序的先验知识。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
void traversal(TreeNode* cur, TreeNode*& pre, int& cnt, int& max_cnt,vector<int>& res)
{
    if(!cur) return;
    traversal(cur->left,pre,cnt,max_cnt,res);
    if(pre)
        cnt = cur->val == pre->val ?  cnt+1: 1 ;
    pre=cur;
    if(cnt>max_cnt)
    {
        max_cnt=cnt;
        res.clear();
        res.push_back(cur->val);
    }   
    else if(cnt == max_cnt )
        res.push_back(cur->val);
    traversal(cur->right,pre,cnt,max_cnt,res);

}
public:
    vector<int> findMode(TreeNode* root) {
        vector<int>res;
        if(!root) return res;
        int count=1;
        int max_cnt=0;
        TreeNode* pre=nullptr;
        traversal(root,pre,count,max_cnt, res);
        return res;
    }
};

执行用时 :32 ms, 在所有 C++ 提交中击败了72.22%的用户 内存消耗 :23MB, 在所有 C++ 提交中击败了95.89%的用户