Easy

题目描述

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

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

假定 BST 满足如下定义：

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

示例 1：

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

示例 2：

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

提示：

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

进阶： 你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）

解题思路

这道题有两种主要思路：

方法一：哈希表统计（简单直观） 使用哈希表统计每个值的出现频率，然后找出最大频率对应的所有值。这种方法简单易懂，但需要额外的存储空间。

方法二：中序遍历（推荐解法） 利用BST的性质，中序遍历可以得到有序序列。在遍历过程中维护当前值、当前频率、最大频率等信息，一次遍历即可找到所有众数。这种方法更高效，空间复杂度更优。

具体实现时，我们维护以下变量：

  • prev：上一个遍历的值
  • count：当前值的频率
  • maxCount：最大频率
  • result：结果数组

当遍历到新值时，重置计数；当频率等于最大频率时，加入结果；当频率大于最大频率时，更新最大频率并重置结果数组。

代码实现

class Solution {
public:
    vector<int> findMode(TreeNode* root) {
        vector<int> result;
        int prev = INT_MIN, count = 0, maxCount = 0;
        
        function<void(TreeNode*)> inorder = [&](TreeNode* node) {
            if (!node) return;
            
            inorder(node->left);
            
            if (prev == node->val) {
                count++;
            } else {
                count = 1;
                prev = node->val;
            }
            
            if (count > maxCount) {
                maxCount = count;
                result.clear();
                result.push_back(node->val);
            } else if (count == maxCount) {
                result.push_back(node->val);
            }
            
            inorder(node->right);
        };
        
        inorder(root);
        return result;
    }
};

class Solution:
    def findMode(self, root: Optional[TreeNode]) -> List[int]:
        def inorder(node):
            if not node:
                return
            
            inorder(node.left)
            
            if self.prev == node.val:
                self.count += 1
            else:
                self.count = 1
                self.prev = node.val
            
            if self.count > self.max_count:
                self.max_count = self.count
                self.result = [node.val]
            elif self.count == self.max_count:
                self.result.append(node.val)
            
            inorder(node.right)
        
        self.prev = None
        self.count = 0
        self.max_count = 0
        self.result = []
        
        inorder(root)
        return self.result

public class Solution {
    private List<int> result = new List<int>();
    private int prev = int.MinValue;
    private int count = 0;
    private int maxCount = 0;
    
    public int[] FindMode(TreeNode root) {
        Inorder(root);
        return result.ToArray();
    }
    
    private void Inorder(TreeNode node) {
        if (node == null) return;
        
        Inorder(node.left);
        
        if (prev == node.val) {
            count++;
        } else {
            count = 1;
            prev = node.val;
        }
        
        if (count > maxCount) {
            maxCount = count;
            result.Clear();
            result.Add(node.val);
        } else if (count == maxCount) {
            result.Add(node.val);
        }
        
        Inorder(node.right);
    }
}

var findMode = function(root) {
    let modes = [];
    let maxCount = 0;
    let currentCount = 0;
    let prevVal = null;
    
    function inorder(node) {
        if (!node) return;
        
        inorder(node.left);
        
        if (prevVal === node.val) {
            currentCount++;
        } else {
            currentCount = 1;
            prevVal = node.val;
        }
        
        if (currentCount > maxCount) {
            maxCount = currentCount;
            modes = [node.val];
        } else if (currentCount === maxCount) {
            modes.push(node.val);
        }
        
        inorder(node.right);
    }
    
    inorder(root);
    return modes;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小说明
时间复杂度O(n)n为节点数，需要遍历所有节点一次
空间复杂度O(h)h为树的高度，递归调用栈的深度

相关题目