Cocolib

Appearance

On this page

二叉搜索树中的众数 ​

Question

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

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

假定 BST 满足如下定义：

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

思路 ​

如果不是二叉搜索树 ​

如果不是二叉搜索树，最直观的方法一定是把这个树都遍历了，用map统计频率，把频率排个序，最后取前面高频的元素的集合。

  1. 这个树都遍历了，用map统计频率
  2. 把统计的出来的出现频率（即map中的value）排个序
  3. 取前面高频的元素

是二叉搜索树 ​

既然是搜索树，它中序遍历就是有序的

js
var findMode = function(root) {
    let count = 0   // 频率
    let pre = null
    let maxcount = 0 //最大频率
    let max = []
    const digui = (cur) =>{     //中序遍历
        if(cur===null)  return
        digui(cur.left)
        if (pre === null) { // 第一个节点
            count = 1;      
        } else if (pre.val === cur.val) { // 与前一个节点数值相同
            count++;
        } else {            // 与前一个节点数值不同
            count = 1;
        }
        if(count===maxcount){
            max.push(cur.val)
        }
        if(count>maxcount){
            max = []
            max.push(cur.val)
            maxcount = count
        }
        pre = cur; // 更新上一个节点
        console.log(count,pre.val)
        digui(cur.right)
    }
    digui(root)
    console.log(max)
    return max
};