二叉搜索树求众数实现中prev变量跟踪逻辑的有效性疑问

结论 #

你提到的场景下prev跟踪逻辑不会失效。

原理说明 #

这个解法的核心依托是合法二叉搜索树的中序遍历特性：无论树的物理结构如何调整，只要符合BST的定义（左子树所有节点值 ≤ 根节点值 ≤ 右子树所有节点值），中序遍历输出的序列一定是非降序排列的。
prev变量记录的是「中序遍历序列的上一个输出节点值」，和树的节点父子物理连接没有关系：

• 中序遍历始终遵循「递归遍历左子树 → 处理当前节点 → 递归遍历右子树」的顺序
• 当处理30节点时，必然已经完成了30左子树的全部遍历，此时prev的值一定是30左子树的最大值（也就是你修改后的25），和30做比较的逻辑完全正确，不会出现跳值、对比错误的问题。

原解法参考代码 #

class Solution {
    Integer prev = null;
    int count = 1;
    int max = 0;
    public int[] findMode(TreeNode root) {
        // 列表支持动态扩容，int数组不支持
        List<Integer> modes = new ArrayList();
        traverse(root, modes);
        int[] result = new int[modes.size()];
        for (int i=0; i<modes.size(); i++){
            result[i] = modes.get(i);
        }
        return result;
    }
    // BST采用中序遍历，得到的节点序列满足左 < 根 < 右的升序规则
    public void traverse(TreeNode root, List<Integer> modes){
        if(root == null) return; // 空节点直接返回

        traverse(root.left,  modes);
        
        if(prev != null){
            if(prev == root.val){
                count ++;
            } else{
                count =1;
            }
        }
        
        if(count > max){
            max = count; 
            modes.clear(); // 找到频次更高的数，清空之前的众数列表
            modes.add(root.val);
        } else if(count == max) { // 找到频次和当前最大值相等的数，加入众数列表
            modes.add(root.val);
        }
        
        prev = root.val; 
        
        traverse( root.right,  modes);
    }
}

内容的提问来源于stack exchange，提问作者Avv