leetcode501.二叉搜索树中的众数：迭代中序遍历的众数追踪与数组动态更新

一、题目深度解析与BST特性利用

题目描述

给定一棵二叉搜索树（BST），找到树中所有出现频率最高的元素（众数）。题目要求：

1. 树中节点的值可能存在重复
2. 众数可能有多个
3. 不使用额外空间（递归栈空间除外）

BST的核心特性应用

二叉搜索树的中序遍历结果是一个严格递增的有序序列。这一特性带来两个关键优势：

1. 相同值的节点连续出现：在中序遍历中，所有重复的节点值会连续被访问
2. 频率统计简化：无需使用哈希表，仅需跟踪当前值的出现次数和最大次数

示例说明

输入BST：

    4/ \2   6/ \ / \
1  3 6  6

中序遍历结果： [1, 2, 3, 4, 6, 6, 6]
众数： [6]（出现3次）

二、迭代解法的核心实现与逻辑框架

完整迭代代码实现

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int[] findMode(TreeNode root) {List<Integer> res = new ArrayList<>(); // 存储众数结果int count = 0; // 当前最大频率int tempCnt = 0; // 当前值的频率Stack<TreeNode> stack = new Stack<>();TreeNode current = root;TreeNode pre = null; // 记录中序遍历的前一个节点stack.push(current); // 初始压入根节点while (!stack.isEmpty()) {current = stack.pop();if (current != null) {// 压栈顺序：右子树 → 当前节点 → null标记 → 左子树if (current.right != null) {stack.push(current.right);}stack.push(current);stack.push(null); // null标记用于触发访问当前节点if (current.left != null) {stack.push(current.left);}} else {// 遇到null标记，处理当前节点current = stack.pop();// 1. 更新当前值的频率if (pre != null && current.val == pre.val) {tempCnt++; // 与前一个节点值相同，频率+1} else {tempCnt = 1; // 新值，频率重置为1}// 2. 更新结果列表if (tempCnt == count) {res.add(current.val); // 当前值频率等于最大频率，加入结果} else if (tempCnt > count) {count = tempCnt; // 更新最大频率res.clear(); // 清空结果列表res.add(current.val); // 添加当前值}pre = current; // 更新前一个节点}}// 将List转换为数组返回return res.stream().mapToInt(Integer::intValue).toArray();}
}

核心设计解析：

1. 双计数器设计：

   • count：记录当前已发现的最大频率
   • tempCnt：记录当前处理值的频率
   • 动态更新count并维护res列表

2. 前置节点比较：

   • pre节点：记录中序遍历的前一个节点
   • 通过比较current.val与pre.val判断是否连续相同值

3. 结果动态更新：

   • 当tempCnt == count时，将当前值加入结果列表
   • 当tempCnt > count时，重置结果列表并添加当前值
   • 使用ArrayList动态调整结果集大小

三、核心问题解析：判断逻辑与结果更新

1. 前置节点比较的关键作用

中序遍历的连续性：

if (pre != null && current.val == pre.val) {tempCnt++;
} else {tempCnt = 1;
}

• 相同值处理：若当前节点值等于前一个节点值，tempCnt递增
• 新值处理：若不同，重置tempCnt为1
• 首次访问：pre为null时，直接视为新值

中序遍历的有序性保证：

• BST的中序遍历确保相同值连续出现
• 无需哈希表，仅通过比较前驱节点即可统计频率

2. 结果列表的动态更新逻辑

频率比较与列表操作：

if (tempCnt == count) {res.add(current.val);
} else if (tempCnt > count) {count = tempCnt;res.clear();res.add(current.val);
}

• 频率相等：当前值频率等于最大频率，直接添加到结果列表
• 频率更高：当前值频率超过最大频率，清空列表并添加当前值
• 动态调整：通过clear()和add()操作保证结果列表始终存储最高频率值

3. 边界条件处理

空树与单节点处理：

• 空树：栈初始为空，直接返回空数组
• 单节点：tempCnt=1，count=1，结果列表正确添加该节点值

多个众数处理：

• 当多个值频率相同时，结果列表会依次添加这些值
• 示例：中序遍历序列为[1,2,2,3,3]，结果列表最终包含[2,3]

四、迭代流程深度模拟：以示例BST为例

示例BST结构：

    4/ \2   6/ \ / \
1  3 6  6

中序遍历过程：

1. 遍历序列：[1, 2, 3, 4, 6, 6, 6]
2. 频率统计与结果更新：
   • 访问1：tempCnt=1，count=1，res=[1]
   • 访问2：tempCnt=1，count=1，res=[1,2]
   • 访问3：tempCnt=1，count=1，res=[1,2,3]
   • 访问4：tempCnt=1，count=1，res=[1,2,3,4]
   • 访问6：tempCnt=1，count=1，res=[1,2,3,4,6]
   • 访问6：tempCnt=2，count=2，res.clear()，res=[6]
   • 访问6：tempCnt=3，count=3，res.clear()，res=[6]
3. 最终结果：res=[6]

五、算法复杂度分析

1. 时间复杂度

• O(n)：每个节点仅被访问一次，n为树的节点数
• 中序遍历过程中每个节点执行常数级操作

2. 空间复杂度

• O(h)：h为树的高度（递归栈深度）
  • 平衡BST：h=logn，空间复杂度O(logn)
  • 最坏情况（退化为链表）：h=n，空间复杂度O(n)

3. 与递归解法对比

方法	优势	劣势
迭代法	避免递归栈溢出，空间更可控	栈操作逻辑较复杂
递归法	代码简洁，符合中序遍历定义	深树可能导致栈溢出

六、核心技术点总结：迭代众数追踪的三大关键

1. 中序遍历的有序性利用

• 相同值连续性：BST中序遍历使相同值连续出现
• 简化频率统计：仅需比较前驱节点即可统计频率
• 时间复杂度优化：从O(nlogn)（排序后统计）降至O(n)

2. 双计数器动态更新

• 频率追踪：tempCnt跟踪当前值频率，count记录最大频率
• 结果维护：通过比较频率动态调整结果列表
• 空间优化：无需存储所有值的频率，仅维护结果列表

3. 结果列表的动态调整

• 清空操作：当发现更高频率时，清空现有结果
• 多众数处理：频率相同时添加多个值
• 列表转数组：最终通过stream API高效转换为数组

七、常见误区与优化建议

1. 错误的频率统计方法

• 误区：使用哈希表统计所有值的频率

  // 错误示例：使用额外空间
  Map<Integer, Integer> freq = new HashMap<>();
  // 遍历树统计频率
  int maxFreq = Collections.max(freq.values());
  // 收集众数
  

• 正确逻辑：利用BST有序性，仅维护当前最大值

2. 结果更新时机错误

• 误区：在遍历过程中提前确定众数
• 正确逻辑：遍历结束后才能确定最终众数
• 示例错误：在访问第一个6时认为其频率最高

3. 优化建议：Morris遍历实现O(1)空间

// 伪代码：Morris遍历实现
public int[] findMode(TreeNode root) {List<Integer> res = new ArrayList<>();int count = 0, tempCnt = 0;TreeNode current = root, pre = null;while (current != null) {if (current.left == null) {// 处理当前节点updateMode(current, res, count, tempCnt);current = current.right;} else {// 寻找前驱节点pre = current.left;while (pre.right != null && pre.right != current)pre = pre.right;if (pre.right == null) {pre.right = current;current = current.left;} else {pre.right = null;// 处理当前节点updateMode(current, res, count, tempCnt);current = current.right;}}}return res.stream().mapToInt(Integer::intValue).toArray();
}

• 优势：空间复杂度优化至O(1)
• 原理：通过线索二叉树实现无栈的中序遍历

八、总结：迭代中序遍历的众数追踪之道

本算法通过迭代实现中序遍历，将BST的众数问题转化为有序序列的频率统计，核心在于：

1. BST有序性的利用：中序遍历结果的有序性是解决问题的关键
2. 双计数器动态更新：通过tempCnt和count动态追踪频率变化
3. 结果列表的智能维护：根据频率关系动态调整结果集

理解这种迭代法的关键是将树的结构特性（BST的有序性）转化为线性序列的频率统计问题。迭代实现避免了递归栈溢出的风险，适合处理大规模数据。在实际工程中，这种基于中序遍历的频率统计方法常用于有序数据的众数分析，尤其是对空间复杂度有严格要求的场景。