501 二叉搜索树中的众数（递归-BST的中序遍历）

川长思鸟来 2023-01-24 04:27 41阅读 0赞

**1. 问题描述：**

给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。假定 BST 有如下定义：结点左子树中所含结点的值小于等于当前结点的值，结点右子树中所含结点的值大于等于当前结点的值，左子树和右子树都是二叉搜索树

**例如：**

给定 BST \[1,null,2,2\],  
1  
\\  
2  
/  
2  
返回\[2\].  
提示：如果众数超过1个，不需考虑输出顺序  
进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/find-mode-in-binary-search-tree

**2. 思路分析：**

题目给出的是**二叉搜索树**，我们需要利用好二叉搜索树的一个特点：二叉搜索树的中序遍历是有序的，所以实际上我们在遍历的时候已知的是一维数组，我们需要求解出一维数组中出现次数最多的数字，有可能存在多个出现次数最多的数字所以我们都需要记录下来。首先我们可以在中序遍历的时候可以维护遍历的前一个数字，根据前一个数字与当前数字是否相同计算出相同数字的长度，当找出所有相同数字的长度之后长度最大的那一段对应的数字就是众数（在递归的时候其实每一次都处理根节点这样就可以更新到当前数字的各个全局变量的值）。结合维护遍历时候的上一个数字，我们还需要记录当前相同数字的长度，当前相同数字出现的最大次数，记录答案的列表，我们在递归完左子树之后处理根节点的情况即可（中序遍历的顺序）。

**3. 代码如下：**

from typing import List
    
    
    class TreeNode:
        def __init__(self, val=0, left=None, right=None):
            self.val = val
            self.left = left
            self.right = right
    
    
    class Solution:
        res = None
        # last记录上一个数字, count记录当前相同数字的长度, maxC记录当前相同数字的最大长度
        last, count, maxC = 0, 0, 0
        
        # 中序遍历在递归完左子树之后处理根节点
        def dfs(self, root: TreeNode):
            if not root: return
            self.dfs(root.left)
            # 第一次遍历的时候判断一下count是否等于0,特判一下
            if self.count == 0 or root.val == self.last:
                self.count += 1
                self.last = root.val
            else:
                self.last = root.val
                self.count = 1
            # 每一次都处理根节点更新对应的全局变量
            if self.count > self.maxC:
                self.res = [root.val]
                self.maxC = self.count
            elif self.count == self.maxC:
                self.res.append(root.val)
            self.dfs(root.right)
    
        # 中序遍历是有序的
        def findMode(self, root: TreeNode) -> List[int]:
            self.res = list()
            self.last = self.count = 0
            self.dfs(root)
            return self.res