首页 > 其他分享 >LeetCode 501. 二叉搜索树中的众数

LeetCode 501. 二叉搜索树中的众数

时间:2023-07-03 22:45:37浏览次数:50  
标签:count pre res 树中 众数 maxc root LeetCode

题目链接:

LeetCode 501. 二叉搜索树中的众数

题意:

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

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

解题思路:

递归法

由于是二叉搜索树,中序遍历是有序的,因此相当于在一个有序的数组上找出众数,利用有序的特性,在遍历二叉树的过程中,

标记上一个节点值 pre(用于判断当前节点是否与上一个节点相同,相同,则众数 +1),当前的众数 conut(记录当前这个数出现的次数),最大的众数maxc(表示树中最大的众数)

思路:

  1. 按照中序遍历,遍历整个二叉树,在遍历过程中记录 precountmaxc
  2. 比较当前节点的值与 pre是否相同,如果相同,则 count 加 1,如果不同,则要比较与 maxc 的大小关系
  3. 如果 count > maxc 说明出现了新的众数,则清空原来的结果数据 res ,将新的众数添加进去
  4. 如果 count == maxc 说明又多了一个众数,将该数加入结果数据,
  5. 最后返回结果数据

递归代码:

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
 //首先 对于二叉搜索树,中序遍历是有序的,因此相当于在一个有序的数组上找出众数
var res []int
var pre,maxc,count int
func findMode(root *TreeNode) []int {
    maxc = 0
    count = 0
    res = []int{}
    dfs(root)
    return res
}

func dfs( root *TreeNode){
    if root == nil {
        return
    }
    // 中序遍历
    dfs(root.Left)
    // 如果是第一个节点,或者当前节点与上一个节点相同,
    if count == 0 || root.Val == pre{
        count++ //当前众数++
        pre = root.Val
    }else{ //如果是一个新的数
        pre = root.Val
        count = 1
    }
    if count > maxc{
        maxc = count
        res = []int{root.Val} //更新结果数组,注意直接将之前的结果数组里面的数据全部删除
    }else if count == maxc{ //如果当前众数与最大众数相同,则放入结果数组
        res = append(res,pre)
    }
    dfs(root.Right)
}

标签:count,pre,res,树中,众数,maxc,root,LeetCode
From: https://www.cnblogs.com/lxing-go/p/17524333.html

相关文章

  • LeetCode 图
    200. 岛屿数量695. 岛屿的最大面积精品题解 https://leetcode.cn/problems/number-of-islands/solution/dao-yu-lei-wen-ti-de-tong-yong-jie-fa-dfs-bian-li-/注意深度优先遍历,对一格陆地(=='1')遍历, 就会把与它连通的所有陆地遍历到,全部标记为2,完成一个岛屿。从而这一次......
  • LeetCode -- 767. 重构字符串
     设字符串s长度为lens可以重构为相邻字符串不同时有字符串中出现次数最多的字符<(len+1)>>1当满足上述条件时候,我们就能对其进行重构重构法:先放置偶数位置,再放置奇数位置c++classSolution{public:stringreorganizeString(strings){vector<i......
  • 【LeetCode剑指offer#05】回文链表的两种解法+删除链表中间节点(链表的基本操作)
    回文链表给你一个单链表的头节点head,请你判断该链表是否为回文链表。如果是,返回true;否则,返回false。示例1:输入:head=[1,2,2,1]输出:true示例2:输入:head=[1,2]输出:false提示:链表中节点数目在范围[1,105]内0<=Node.val<=9思路将值复制到数组中后用双指针......
  • 【leetcode】【1474】【删除链表 M 个节点之后的 N 个节点】
    c++第一个方法#include<algorithm>#include<iostream>#include<memory>#include<vector>//Definitionforsingly-linkedlist.structListNode{intval;ListNode*next;ListNode():val(0),next(nullptr){}Li......
  • 【笔试实战】LeetCode题单刷题-编程基础 0 到 1【一】
    1768. 交替合并字符串题目链接1768. 交替合并字符串题目描述给你两个字符串 word1 和 word2 。请你从 word1 开始,通过交替添加字母来合并字符串。如果一个字符串比另一个字符串长,就将多出来的字母追加到合并后字符串的末尾。返回 合并后的字符串 。示例1:输入:wor......
  • 【leetcode】【876】【链表的中间结点】
    c++第一个方法#include<algorithm>#include<iostream>#include<memory>#include<vector>//Definitionforsingly-linkedlist.structListNode{intval;ListNode*next;ListNode():val(0),next(nullptr){}Li......
  • LeetCode/和等于目标值的质数对
    给你一个整数n,如果两个整数x和y满足下述条件,则认为二者形成一个质数对:1<=x<=y<=nx+y==nx和y都是质数请你以二维有序列表的形式返回符合题目要求的所有[xi,yi],列表需要按xi的非递减顺序排序。如果不存在符合要求的质数对,则返回一个空数组。1.埃氏筛预......
  • LeetCode-Python-#27 移除元素
    题目描述给定一个数列nums和数值val,消除数列nums中与数值 val相同的元素,最终返回新数列的长度;要求:不能开辟空间分配新的数列,必须改变原输入nums数列;并对修改后的nums数列的元素顺序没有要求,可以被修改。Examplesnums=[3,2,2,3; val=3 则返回长度为2;nums=[0,1,2,2,3,0,4,2]......
  • 二叉树中的递归算法(二)
    从二叉树遍历看递归二叉树二叉树(binarytree)是指树中节点的度不大于2的有序树,它是一种最简单且最重要的树。二叉树的递归定义为:二叉树是一棵空树,或者是一棵由一个根节点和两棵互不相交的,分别称作根的左子树和右子树组成的非空树;左子树和右子树又同样都是二叉树。二叉树的遍......
  • leetcode集训
    设定目标:在开始做题之前,设定一个明确的目标是很重要的。你可以考虑设定一个每日或每周的目标,例如解决一定数量的问题,提高通过率等。理解问题:在开始解题之前,确保你完全理解了题目要求和限制条件。仔细阅读问题描述,明确输入和输出的格式,以及特定的边界情况。思考不同的解决方法:对于每......