题目

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

  • 结点左子树中所含节点的值 小于等于 当前节点的值
  • 结点右子树中所含节点的值 大于等于 当前节点的值
  • 左子树和右子树都是二叉搜索树

解题思路

其实这题解题思路很简单，就是遍历二叉树，将遍历到的值在哈希表中计数，最后输出众数即可。

代码

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def findMode(self, root: Optional[TreeNode]) -> List[int]:
        cnt = defaultdict(int)
        def dfs(root):
            if root is None: return
            cnt[root.val] += 1
            dfs(root.left)
            dfs(root.right)
        dfs(root)
        max = -inf
        ans = []
        for x, c in cnt.items():
            if c > max:
                max = c
                ans = [x]
            elif c == max:
                ans.append(x)
        return ans

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<int> findMode(TreeNode* root) {
        unordered_map<int, int> cnt;
        vector<int> ans;
        dfs(root, cnt);
        int Max = INT_MIN;
        for (auto &[x, c]: cnt) {
            if (c > Max) {
                Max = c;
                while (!ans.empty()) {
                    ans.pop_back();
                }
                ans.push_back(x);
            } else if (c == Max) {
                ans.push_back(x);
            }
        }
        return ans;
    }
    void dfs(TreeNode* root, unordered_map<int, int>& cnt) {
        if (root == NULL) return;
        ++cnt[root->val];
        dfs(root->left, cnt);
        dfs(root->right, cnt);
    }
};

Go

func findMode(root *TreeNode) []int {
    hash := make(map[int]int)
    dfs(root, hash)
    max := math.MinInt64
    ans := make([]int, 0, 0)
    for x, c := range hash {
        if c > max {
            ans = make([]int, 0, 0)
            ans = append(ans, x)
            max = c
        } else if c == max {
            ans = append(ans, x)
        }
    }
    return ans
}
func dfs(node *TreeNode, hash map[int]int){
    if (node == nil) {return}
        hash[node.Val]++
        dfs(node.Left, hash)
        dfs(node.Right, hash)
}