专栏首页眯眯眼猫头鹰的小树杈leetcode501. Find Mode in Binary Search Tree

leetcode501. Find Mode in Binary Search Tree

题目要求

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.

For example: Given BST [1,null,2,2],

   1
    \
     2
    /
   2

return [2].

Note: If a tree has more than one mode, you can return them in any order.

Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).

现有一个可以包含重复元素的二叉查找树,该二叉查找树满足所有左节点的值均小于等于父节点,所有右节点均大于等于父节点。现要求找出所有出现次数最多的值。

思路和代码

题目中有一个额外的要求,就是只用O(1)的空间复杂度来完成这次计算。这里就复述一下在回答里面一个非常非常棒的解答。即通过两次中序遍历来完成。第一次中序遍历将计算出出现最多的次数。第二次中序遍历则将统计的次数等于第一次计算出的最多次数的结果相等的值加入结果集中。

    int maxCount;
    int curCount;
    int curValue;
    int[] result;
    int modeCount;

    public int[] findMode(TreeNode root) {
        inorder(root);
        result = new int[modeCount];
        curCount = 0;
        modeCount = 0;
        inorder(root);
        return result;
    }

    private void inorder(TreeNode node) {
        if (node == null) {
            return;
        }
        inorder(node.left);
        handle(node.val);
        inorder(node.right);
    }

    private void handle(int val) {
        if (val != curValue) {
            curCount = 0;
            curValue = val;
        }
        curCount++;
        if (curCount > maxCount) {
            modeCount = 1;
            maxCount = curCount;
        }else if (curCount == maxCount) {
            if (result != null) {
                result[modeCount] = curValue;
            }
            modeCount++;
        }
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode477. Total Hamming Distance

    计算N个数字之间的汉明码距离之和。 汉明码是指两个数字的二进制表示形式中,在对应位置上值不同的数量总和。如2和4,4的二进制表达式为100, 2的二进制表达式0...

    眯眯眼的猫头鹰
  • leetcode502. IPO

    Suppose LeetCode will start its IPO soon. In order to sell a good price of its s...

    眯眯眼的猫头鹰
  • leetcode381. Insert Delete GetRandom O(1) - Duplicates allowed

    设计一个数据结构,支持能够在O(1)的时间内完成对数字的插入,删除和获取随机数的操作,允许插入重复的数字,同时要求每个数字被随机获取的概率和该数字当前在数据结构...

    眯眯眼的猫头鹰
  • 最短路专题2 | CodeForces 449B - SPFA算法

    Jzzhu is the president of country A. There are n cities numbered from 1 to n in ...

    ACM算法日常
  • HDUOJ-----(1162)Eddy's picture(最小生成树)

    Eddy's picture Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/327...

    Gxjun
  • 聊聊flink的ScheduledExecutor

    java.base/java/util/concurrent/Executor.java

    codecraft
  • 简易 bokeh 图像散景效果算法实现

    bokeh百度百科的解释 摄影镜头光圈大小和拍摄距离决定了拍摄时的景深,相对于焦点位置,焦点前与焦点后的被拍摄物体会显得模糊,这个模糊区域被称为焦外。 焦外...

    cpuimage
  • 深度单图像处理(CS)

    多年来,由于这项任务的受欢迎程度和商业重要性,图像处理吸引了许多研究。已有许多基于深度神经网络的方法用于许多图像处理任务。深度方法的主要问题是需要训练来自与目标...

    DDDDDaemon
  • 如何关闭SAP ICF调试

    I checked the trace but there is no long running statement on CRMD_ORDER_INDEX.

    Jerry Wang
  • AtomicInteger源码分析详解

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    suveng

扫码关注云+社区

领取腾讯云代金券