写点什么

头脑风暴:二叉搜索树中的众数

  • 2022 年 8 月 26 日
    江苏
  • 本文字数:1140 字

    阅读完需:约 4 分钟

头脑风暴:二叉搜索树中的众数

题目

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


假定 BST 有如下定义:


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


例如:


给定 BST [1,null,2,2],


   1    \     2    /   2
复制代码


返回[2].

解题思路

根据题意,我们一定能想到一个最朴素的做法,由于本题给出的是一棵二叉搜索树,所以我们首先想到的就是利用中序排序,可以得到一个有序的数组,既然要求这个有序数组中出现频率最高的值,我们可以用以下思路来解答:


  1. 通过中序遍历,将二叉搜索树转换到一个有序数组中;

  2. 利用哈希表,遍历该有序数组,求得每个值出现的次数;

  3. 遍历该哈希表,然后得出出现频率最高的值;

代码实现


/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { private List<Integer> list; public int[] findMode(TreeNode root) { list = new ArrayList(); inOrder(root);
Map<Integer, Integer> map = new HashMap(); int maxLen = Integer.MIN_VALUE; // 扫描有序数组,求得最高频率 for (int value :list) { map.put(value, map.getOrDefault(value, 0) + 1); if (maxLen < map.get(value)) { maxLen = map.get(value); } }
if (maxLen > 0) { // 遍历哈希表,得出出现频率最高的值 List<Integer> ans = new ArrayList<>(); for (int b:map.keySet()) { if (map.get(b).equals(maxLen)) { ans.add(b); } } int answ[] = new int[ans.size()]; for (int i = 0; i < ans.size(); i++) { answ[i] = ans.get(i); } return answ; }
return new int[0]; } // 中序遍历 public void inOrder(TreeNode node){ if (node == null) return; inOrder(node.left); list.add(node.val); inOrder(node.right); }}
复制代码

最后

复杂度分析:


  • 时间复杂度:O(n)。即遍历这棵树的复杂度。

  • 空间复杂度:O(n)。即递归的栈空间的空间代价加上哈希表的空间。

发布于: 刚刚阅读数: 4
用户头像

佛系编码 2019.05.13 加入

红鲤鱼与绿鲤鱼与驴。

评论

发布
暂无评论
头脑风暴:二叉搜索树中的众数_算法_HelloWorld杰少_InfoQ写作社区