简体中文

二叉搜索树中的众数

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

假定BST有如下定义：

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

示例

给定BST [1,null,2,2]，返回[2]。

1 \ 2 / 2

注意

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

题解

/**
 * 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) {
    if(!root) return [];
    var cur = Infinity;
    var curCounter = 0;
    var maxValues = [];
    var maxValuesCounter = -Infinity;
    var dfs = (root) => {
        if(!root) return void 0;
        if(root.left) dfs(root.left);
        if(cur === root.val){
            ++curCounter;
        }else{
            cur = root.val;
            curCounter = 0;
        }
        if(curCounter >= maxValuesCounter){
            if(curCounter === maxValuesCounter) maxValues.push(root.val);
            else maxValues = [root.val];
            maxValuesCounter = curCounter;
        }
        if(root.right) dfs(root.right);
    }
    dfs(root);
    return maxValues;
};

思路

本题的题目中有一个进阶条件：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内），如果不考虑这个进阶条件的话，直接遍历一遍二叉树并且顶一个哈希表将遍历过的值以及出现的次数记录，之后再遍历一遍哈希表取出众数即可，考虑到这个进阶条件，那么就需要定义一些变量保存当前的状态，判断哪些条件符合要求，置入返回值，当对二叉搜索树进行二叉树中序遍历时，能够得到一个有序的序列，通过数列有序以及存储当前状态的变量即可达到目标，此外还需要注意的是题目要求是返回一个数组，也就说众数可能有多个。首先判断如果是空树直接返回空数组，定义当前值为Infinity无穷大，定义当前值计数器为0，最大值数组为空数组，最大值计数器为-Infinity负无穷大，之后定义深度递归遍历，首先判断节点不存在则直接返回，若左节点存在则向左递归，之后定义的处理位置即中序遍历，如果当前结点值与存储的遍历当前节点值相同则将计数器递增，否则将当前值置数为节点值，将计数器置0，如果当前计数器大于等于最大值的计数器则进入条件，如果这两个值相等，那么将该值置入最大值数组，否则将最大值数组置换为只有该值的数组，然后将最大值计数器赋值当前值计数器，之后判断右节点存在则向右递归，最终返回最大值数组即可。

每日一题

https://github.com/WindrunnerMax/EveryDay

参考

https://leetcode-cn.com/problems/find-mode-in-binary-search-tree