( “树” 之 BST) 501. 二叉搜索树中的众数 ——【Leetcode每日一题】

二叉查找树（BST）：根节点大于等于左子树所有节点，小于等于右子树所有节点。
二叉查找树中序遍历有序。

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

难度：简单

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

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

假定 BST 满足如下定义：

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

示例 1：

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

示例 2：

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

提示：

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

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

💡思路：

中序遍历，边遍历边统计：

要设置三个变量：curCnt表示当前个数；maxCnt表示最大个数；preNode表示前一个结点：

• 如果当前结点值等于前一个结点值，则curCnt++，否则curCnt置为1重新计数；
• 如果当前个数curCnt大于最大个数maxCnt，则将数组清空，添加当前节点值；
• 如果当前个数curCnt大于最大个数maxCnt，则不需要清空，在数组后面添加就行；

🍁代码：(Java、C++)

Java

class Solution {private int curCnt = 1;private int maxCnt = 1;private TreeNode preNode = null;public int[] findMode(TreeNode root) {List<Integer> maxCntNums = new ArrayList<>();inOrder(root, maxCntNums);int[] ret = new int[maxCntNums.size()];int idx = 0;for (int num : maxCntNums) {ret[idx++] = num;}return ret;}private void inOrder(TreeNode node, List<Integer> nums) {if (node == null) return;inOrder(node.left, nums);if (preNode != null) {if (preNode.val == node.val) curCnt++;else curCnt = 1;}if (curCnt > maxCnt) {maxCnt = curCnt;nums.clear();nums.add(node.val);} else if (curCnt == maxCnt) {nums.add(node.val);}preNode = node;inOrder(node.right, nums);}
}

C++

class Solution {
public:int curCnt = 1;int maxCnt = 1;TreeNode* preNode = nullptr;vector<int> findMode(TreeNode* root) {vector<int> ans;inOrder(root, ans);return ans;}void inOrder(TreeNode* root, vector<int>& ans){if(root == nullptr) return;inOrder(root->left, ans);if(preNode != nullptr){if(root->val == preNode->val) curCnt++;else curCnt = 1;}if(curCnt > maxCnt){maxCnt = curCnt;ans.clear();ans.push_back(root->val);}else if(curCnt == maxCnt){ans.push_back(root->val);}preNode = root;inOrder(root->right, ans);}
};

🚀 运行结果：

🕔 复杂度分析：

• 时间复杂度：$O(n)$：即遍历这棵树的复杂度。
• 空间复杂度：$O(1)$：如果调用栈的开销不被计算在内，储存结果的数组也不计算，空间复杂度为$O(1)$。

题目来源：力扣。

放弃一件事很容易，每天能坚持一件事一定很酷，一起每日一题吧！
关注我 leetCode专栏，每日更新！

注： 如有不足，欢迎指正！