501. 二叉搜索树中的众数
程序员文章站
2022-05-20 16:14:41
...
题目链接:https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/
给定一个有相同值的二叉搜索树(BST),找出 BST 中的所有众数(出现频率最高的元素)。
假定 BST 有如下定义:
-
结点左子树中所含结点的值小于等于当前结点的值
-
结点右子树中所含结点的值大于等于当前结点的值
-
左子树和右子树都是二叉搜索树
例如:
给定 BST [1,null,2,2],
1
\
2
/
2
返回[2].
提示:如果众数超过1个,不需考虑输出顺序
进阶:你可以不使用额外的空间吗?(假设由递归产生的隐式调用栈的开销不被计算在内)
###########################################################################
因为二叉搜索树,中序遍历的话得到的值是逐渐增加的,可以利用这个特点。我写的就是在遍历树,普通的二叉树也适用。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int[] findMode(TreeNode root) {
Map<Integer,Integer> m=new HashMap<>();
put(root,m);
int max=0;
for(int i:m.values()){
if(i>max){
max=i;
}
}
List<Integer> l=new ArrayList<>();
for(int j:m.keySet()){
if(m.get(j)==max){
l.add(j);
}
}
int[] r=new int[l.size()];
for(int k=0;k<l.size();k++){
r[k]=l.get(k);
}
return r;
}
public void put(TreeNode root,Map m){
if(root!=null){
put(root.left,m);
if(m.containsKey(root.val)){
m.put(root.val,(int)(m.get(root.val))+1);
}else{
m.put(root.val,1);
}
put(root.right,m);
}
}
}
推荐阅读
-
Python中的二叉树查找算法模块使用指南
-
Python利用前序和中序遍历结果重建二叉树的方法
-
Python实现查找二叉搜索树第k大的节点功能示例
-
C语言实现线索二叉树的前中后创建和遍历详解
-
荐 Java刷题笔记15:不同的二叉搜索树( Unique Binary Search Trees)
-
Python实现输入二叉树的先序和中序遍历,再输出后序遍历操作示例
-
[PHP] 算法-根据前序和中序遍历结果重建二叉树的PHP实现
-
python3实现在二叉树中找出和为某一值的所有路径
-
【算法】二叉树的前序、中序、后序、层序遍历和还原。
-
Python二叉树的遍历操作示例【前序遍历,中序遍历,后序遍历,层序遍历】