1. 题目描述

给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。假定 BST 有如下定义：

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

例如：给定 BST [1,null,2,2],

  1.    1
  2.     \
  3.      2
  4.     /
  5.    2
  6. 返回[2].

提示：如果众数超过1个，不需考虑输出顺序
进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）

2. 解题思路

对于这道题目，我们可以对二叉树进行深度优先遍历，在遍历过程中，初始化一个max，用来保存当前元素出现的最大的次数，将二叉树值与对应的次数保存在一个map中，最后我们遍历一遍这个map，将所有次数与max相等的值都保存在res中即可。

复杂度分析：

  • 时间复杂度：O(n)，其中n是这棵树的节点数量，我们需要遍历整棵树。
  • 空间复杂度：O(n)，其中n是这棵树的节点数量，这里需要的是递归的栈空间的空间代价。

    3. 代码实现

    ```javascript /**
    • Definition for a binary tree node.
    • function TreeNode(val) {
    • this.val = val;
    • this.left = this.right = null;
    • } / /*
    • @param {TreeNode} root
    • @return {number[]} */

var findMode = function(root) { let map = {}, max = 0, res = []

  1. const dfs = (root) => {
  2.     if(!root){
  3.         return []
  4.     }
  5.     map[root.val] ? map[root.val] += 1 : map[root.val] = 1;
  7.     max = Math.max(max, map[root.val])
  8.     dfs(root.left)
  9.     dfs(root.right)
  10. }
  11. dfs(root)
  13. for(let key in map){
  14.     if(max === map[key]){
  15.         res.push(key)
  16.     }
  17. }
  18. return res

}; ```

4. 提交结果

image.png