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).

思路和代码

```    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 ...

• HDUOJ-----(1162)Eddy's picture（最小生成树）

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

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

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

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

• 深度单图像处理（CS）

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

• 如何关闭SAP ICF调试

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

• AtomicInteger源码分析详解

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