每日一练:LeeCode-501、二叉搜索树中的众数【二叉搜索树+pre辅助节点+DFS】

2024-02-19 07:28

本文主要是介绍每日一练:LeeCode-501、二叉搜索树中的众数【二叉搜索树+pre辅助节点+DFS】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

本文是力扣LeeCode-LeeCode-501、二叉搜索树中的众数【二叉搜索树+pre辅助节点+DFS】 学习与理解过程,本文仅做学习之用,对本题感兴趣的小伙伴可以出门左拐LeeCode。

给你一个含重复值的二叉搜索树(BST)的根节点 root ,找出并返回 BST 中的所有 众数(即,出现频率最高的元素)。

如果树中有不止一个众数,可以按 任意顺序 返回

假定 BST 满足如下定义:

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

示例 1:
在这里插入图片描述

输入:root = [1,null,2,2]
输出:[2]

示例 2:

输入:root = [0]
输出:[0]

提示:

  • 树中节点的数目在范围 [1, 104] 内
  • -10^5 <= Node.val <= 10^5

思路

思路一(普通二叉树)

首先这道题要求的是二叉搜索树,如果为我们直接把它当成一颗普通⼆叉树,也是可以直接解决的遍历存数组+使用map统计频率+最后取高频的一个或者多个数

思路二(二叉搜索树)

  • 既然是搜索树,它中序遍历就是有序的
  • 遍历有序数组的元素出现频率从头遍历,那么⼀定是相邻两个元素作⽐较,然后就把出现频率最⾼的元素输出即可
  • 出现相邻两个元素的情况,可以使⽤pre指针和cur指针的技巧了
  • 需要注意初始化的时候pre = NULL,实际上比较的是第⼀个元素

统计众数出现次数的代码:

        if (pre==null){	// 第⼀个节点count=1;	// 频率为1} else if (pre.val==cur.val) {	// 与前⼀个节点数值相同count++;} else{			// 与前⼀个节点数值不同,则复原count=1;}pre = cur;		// 更新上⼀个节点

本题要求的是:返回众数集合/数组
1、正常逻辑第一遍先找出最⼤频率maxCount,然后重新遍历⼀遍数组把出现频率为maxCount的元素放进众数集合里,最终需要两遍

2、遍历一次数组(只需要遍历⼀遍⼆叉搜索树,就求出了众数的集合)

  • maxCount需要最⼤频率的时候保存
  • 频率count ⼤于 maxCount的时候,不仅要更新maxCount,⽽且要清空结果集,留着之前的结果集不对

实现代码

class Solution {TreeNode pre = null;int count = 0;		 // 统计频率int maxCount = 0;	 // 最⼤频率List<Integer> resList = new ArrayList<>();public int[] findMode(TreeNode root) {searchBST(root);	int[] result = new int[resList.size()];for (int i=0;i<resList.size();i++){result[i] = resList.get(i);}return result;}void searchBST(TreeNode cur){if (cur==null)return;searchBST(cur.left);	// 左// 中if (pre==null){		// 第⼀个节点count=1;} else if (pre.val==cur.val) {	// 与前⼀个节点数值相同count++;} else{		// 与前⼀个节点数值不同count=1;}pre = cur;		// 更新上⼀个节点if (maxCount==count)resList.add(cur.val);	// 如果和最⼤值相同,放进resList中if (count>maxCount){	// 计数⼤于最⼤值频率maxCount = count;	// 更新最⼤频率resList.clear();	// 很关键的⼀步,不要忘记清空resList,之前resList⾥的元素都失效了resList.add(cur.val);}searchBST(cur.right);	// 右return;}
}

最重要的一句话:做二叉树的题目,首先需要确认的是遍历顺序
大佬们有更好的方法,请不吝赐教,谢谢

这篇关于每日一练:LeeCode-501、二叉搜索树中的众数【二叉搜索树+pre辅助节点+DFS】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/723936

相关文章

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

hdu1240、hdu1253(三维搜索题)

1、从后往前输入,(x,y,z); 2、从下往上输入,(y , z, x); 3、从左往右输入,(z,x,y); hdu1240代码如下: #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc

day-51 合并零之间的节点

思路 直接遍历链表即可,遇到val=0跳过,val非零则加在一起,最后返回即可 解题过程 返回链表可以有头结点,方便插入,返回head.next Code /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}*

hdu 2489 (dfs枚举 + prim)

题意: 对于一棵顶点和边都有权值的树,使用下面的等式来计算Ratio 给定一个n 个顶点的完全图及它所有顶点和边的权值,找到一个该图含有m 个顶点的子图,并且让这个子图的Ratio 值在所有m 个顶点的树中最小。 解析: 因为数据量不大,先用dfs枚举搭配出m个子节点,算出点和,然后套个prim算出边和,每次比较大小即可。 dfs没有写好,A的老泪纵横。 错在把index在d

poj 3050 dfs + set的妙用

题意: 给一个5x5的矩阵,求由多少个由连续6个元素组成的不一样的字符的个数。 解析: dfs + set去重搞定。 代码: #include <iostream>#include <cstdio>#include <set>#include <cstdlib>#include <algorithm>#include <cstring>#include <cm

hdu 4517 floyd+记忆化搜索

题意: 有n(100)个景点,m(1000)条路,时间限制为t(300),起点s,终点e。 访问每个景点需要时间cost_i,每个景点的访问价值为value_i。 点与点之间行走需要花费的时间为g[ i ] [ j ] 。注意点间可能有多条边。 走到一个点时可以选择访问或者不访问,并且当前点的访问价值应该严格大于前一个访问的点。 现在求,从起点出发,到达终点,在时间限制内,能得到的最大

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close

hdu4277搜索

给你n个有长度的线段,问如果用上所有的线段来拼1个三角形,最多能拼出多少种不同的? import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;

hihocoder1050 : 树中的最长路

时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 上回说到,小Ho得到了一棵二叉树玩具,这个玩具是由小球和木棍连接起来的,而在拆拼它的过程中,小Ho发现他不仅仅可以拼凑成一棵二叉树!还可以拼凑成一棵多叉树——好吧,其实就是更为平常的树而已。 但是不管怎么说,小Ho喜爱的玩具又升级换代了,于是他更加爱不释手(其实说起来小球和木棍有什么好玩的是吧= =)。小Ho手