LeetCode题练习与总结：二叉搜刮树中的众数--501

一、标题形貌

给你一个含重复值的二叉搜刮树（BST）的根节点 root ，找出并返回 BST 中的全部 众数（即，出现频率最高的元素）。
假如树中有不止一个众数，可以按 恣意序次 返回。
假定 BST 满意如下界说：

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

示例 1：

1. <strong>输入：</strong>root = [1,null,2,2]
2. <strong>输出：</strong>[2]

复制代码

示例 2：

1. <strong>输入：</strong>root = [0]
2. <strong>输出：</strong>[0]

复制代码

提示：

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

二、解题思绪

由于给定的二叉树是二叉搜刮树（BST），我们可以使用中序遍历的特性来办理这个标题。中序遍历BST会得到一个有序的数组，因此我们可以在这个有序数组中找到众数。
步调如下：

• 举行中序遍历，记录每个节点的值以及它们出现的频率。
  
• 在遍历过程中，维护当前节点的值、当前值的出现次数以及最大出现次数。
  
• 假如当前值的出现次数大于最大出现次数，则更新最大出现次数，并清空结果列表，将当前值参加结果列表。
  
• 假如当前值的出现次数即是最大出现次数，则将当前值参加结果列表。
  
• 遍历竣过后，返回结果列表。
  

三、详细代码

1. import java.util.ArrayList;
2. import java.util.List;
4. class Solution {
5.     private int base, count, maxCount;
6.     private List<Integer> answer = new ArrayList<>();
8.     public int[] findMode(TreeNode root) {
9.         inorder(root);
10.         int[] modes = new int[answer.size()];
11.         for (int i = 0; i < answer.size(); ++i) {
12.             modes[i] = answer.get(i);
13.         }
14.         return modes;
15.     }
17.     private void inorder(TreeNode root) {
18.         if (root == null) {
19.             return;
20.         }
21.         inorder(root.left);
22.         update(root.val);
23.         inorder(root.right);
24.     }
26.     private void update(int x) {
27.         if (x == base) {
28.             count++;
29.         } else {
30.             count = 1;
31.             base = x;
32.         }
33.         if (count == maxCount) {
34.             answer.add(base);
35.         }
36.         if (count > maxCount) {
37.             maxCount = count;
38.             answer.clear();
39.             answer.add(base);
40.         }
41.     }
42. }

复制代码

在这段代码中，inorder 方法用于中序遍历二叉树，update 方法用于更新当前值的出现次数，并根据情况更新结果列表。末了，将结果列表转换为数组并返回。
四、时间复杂度和空间复杂度

1. 时间复杂度

• 中序遍历：在inorder方法中，我们对每个节点举行一次访问。由于二叉搜刮树的中序遍历会访问树中的每个节点一次，以是时间复杂度为O(n)，此中n是树中节点的数量。
  
• 更新操纵：在update方法中，对于每个节点，我们实行常数时间的操纵，即比力和更新当前节点的值以及相应的计数。因此，update方法的总时间复杂度也是O(n)。
  

综上所述，整个算法的时间复杂度是O(n)，由于中序遍历和更新操纵都是线性的。
2. 空间复杂度

• 栈空间：在最坏情况下，二叉树大概退化成一条链，因此递归的中序遍历将使用O(h)的空间，此中h是树的高度。在最坏情况下，h可以即是n（当树是线性的），以是空间复杂度是O(n)。
  
• 结果列表：在answer列表中，我们存储了全部众数。在最坏的情况下，假如全部节点的值都雷同，那么众数将是全部节点，answer列表的巨细将是O(n)。
  
• 辅助变量：base, count, maxCount这些变量使用了常数空间。
  

因此，总的空间复杂度是O(n)，这是由递归栈和结果列表的巨细决定的。在最好情况下，假如树是完全均衡的，那么栈空间将是O(log n)，但结果列表的巨细仍旧是O(n)，以是总的空间复杂度仍旧是O(n)。
五、总结知识点

• 类界说：界说了一个Solution类，此中包罗相识决特定标题标方法和变量。
  
• 成员变量：类中界说了几个成员变量来存储遍历过程中的当前值（base）、当前值的出现次数（count）、最大出现次数（maxCount）以及存储众数的列表（answer）。
  
• 递归方法：inorder方法是一个递归方法，用于举行二叉树的中序遍历。
  
• 二叉树的中序遍历：中序遍历二叉树是一种深度优先搜刮计谋，它起首访问左子树，然后访问当前节点，末了访问右子树。
  
• 条件语句：if-else语句用于判断当前节点的值是否与前一个节点的值雷同，并据此更新出现次数。
  
• 列表操纵：使用List接口和ArrayList类来存储众数。add方法用于向列表中添加元素，clear方法用于清空列表。
  
• 数组操纵：将List中的元素复制到数组中，以便返回。
  
• 算法逻辑：通过维护一个最大出现次数和当前出现次数，来找到并更新众数。
  
• 整数范例：使用int范例来存储节点的值、计数和最大计数。
  
• 方法重载：update方法被重载用于更新当前值的出现次数和最大出现次数。
  
• 递归竣事条件：在inorder方法中，递归的竣事条件是当遇到一个null节点时。
  

以上就是办理这个标题标详细步调，盼望可以大概为各位提供启发和资助。