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.
1
For example:
2
Given BST [1,null,2,2],
3
​
4
   1
5
    \
6
     2
7
    /
8
   2
9
 
10
​
11
return [2].
12
​
13
Note: If a tree has more than one mode, you can return them in any order.
Copied!
Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count)
适应于任何树的方法，直接遍历法。
1
/**
2
 * Definition for a binary tree node.
3
 * struct TreeNode {
4
 *     int val;
5
 *     TreeNode *left;
6
 *     TreeNode *right;
7
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8
 * };
9
 */
10
class Solution {
11
unordered_map<int,int>all;
12
void traversal(TreeNode* root)
13
{
14
    if(!root) return;
15
    all[root->val]++;
16
    traversal(root->left);
17
    traversal(root->right);
18
}
19
public:
20
    vector<int> findMode(TreeNode* root) {
21
        vector<int>res;
22
        if(!root) return res;
23
        traversal(root);
24
        int count=0;
25
        for(auto& a: all)
26
        {
27
            count = max(count, a.second);
28
        }
29
        for(auto& a:all)
30
            if(a.second == count) res.push_back(a.first);
31
        return res;
32
    }
33
};
Copied!
执行用时 :52 ms, 在所有 C++ 提交中击败了22.86%的用户
内存消耗 :27.1 MB, 在所有 C++ 提交中击败了12.78%的用户
考虑到是BST，可以充分利用其已经排好序的先验知识。
1
/**
2
 * Definition for a binary tree node.
3
 * struct TreeNode {
4
 *     int val;
5
 *     TreeNode *left;
6
 *     TreeNode *right;
7
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8
 * };
9
 */
10
class Solution {
11
void traversal(TreeNode* cur, TreeNode*& pre, int& cnt, int& max_cnt,vector<int>& res)
12
{
13
    if(!cur) return;
14
    traversal(cur->left,pre,cnt,max_cnt,res);
15
    if(pre)
16
        cnt = cur->val == pre->val ?  cnt+1: 1 ;
17
    pre=cur;
18
    if(cnt>max_cnt)
19
    {
20
        max_cnt=cnt;
21
        res.clear();
22
        res.push_back(cur->val);
23
    }   
24
    else if(cnt == max_cnt )
25
        res.push_back(cur->val);
26
    traversal(cur->right,pre,cnt,max_cnt,res);
27
​
28
}
29
public:
30
    vector<int> findMode(TreeNode* root) {
31
        vector<int>res;
32
        if(!root) return res;
33
        int count=1;
34
        int max_cnt=0;
35
        TreeNode* pre=nullptr;
36
        traversal(root,pre,count,max_cnt, res);
37
        return res;
38
    }
39
};
Copied!
执行用时 :32 ms, 在所有 C++ 提交中击败了72.22%的用户
内存消耗 :23MB, 在所有 C++ 提交中击败了95.89%的用户

500.Keyboard Row

504.Base 7

Last modified 5mo ago

Copy link