在二叉搜索树中查找模式

Question

我看到这个问题已经出现在这个网站上，但我想讨论一个关于在下面的代码中跟踪 prev 值的问题。给定以下用于在二叉搜索树中查找 Mode 的解决方案，

class Solution {
    Integer prev = null;
    int count = 1;
    int max = 0;
    public int[] findMode(TreeNode root) {
         //this is expandable, but int [] array is not expandable
        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;

    }
    //In BST, do inorder since that way nodes will be sorted L < root < R
    public void traverse(TreeNode root, List<Integer> modes){
        if(root == null) return; //dont do anything

        traverse(root.left,  modes);
        
        if(prev != null){
            if(prev == root.val){
                count ++;
            } else{
                count =1;
            }
        }
        
        if(count > max){
            max = count; 
            modes.clear(); //delete all previous modes as we find a new one
            modes.add(root.val);
        } else if(count == max) { // we find another mode that has same # of occurrences
            modes.add(root.val);
        }
        
        prev = root.val; 
        
        traverse( root.right,  modes);
    }
}

现在，prev 变量应该捕获前一个节点值，这样当我们进入节点左侧 child 时，如代码所示，我们将立即比较它在该节点的左侧 child。例如，如果prev = 5，那么一旦我们上升到10，新的prev是prev = root.val;，那么我们就得到10的右边child 15。但是我们不比较prev到 15，但到 10，因为我们立即在代码中向左移动一次，所以我们在 if(prev == root.val) 行中比较 prev = 10 和 node.val。我们从那里开始所有其他节点。

问题：假设紧邻30的结点是25而不是20，那么这里使用的trick解决方案在这种情况下不起作用，请问您怎么看？

Answer 1

该算法正在执行有序树遍历，它是这样做的：

通过递归调用中序函数遍历左子树
访问当前节点的数据部分。
通过递归调用中序函数遍历右子树

在二叉搜索树中，由于节点的顺序，中序遍历是以升序.

访问节点

我认为这张图片（由 Wikipedia 提供）将有助于解释正在发生的事情：

中序遍历会按照以下顺序访问节点：

A、B、C、D、E、F、G、H、I；

现在由于我们访问的节点是按升序排序的，重复项 将被组合在一起。因此，我们只需要将当前节点与前一个节点进行比较，找出重复项即可。

在您的第一个示例树中，按以下顺序访问节点： 5、10、10、12、15、15、16、18、20、20、20、20、25、28、30、32。众数为20.

在您的第二个示例树中，按以下顺序访问节点： 5、10、10、12、15、15、16、18、20、20、20、25、30、32。众数为20.

在二叉搜索树中查找模式

Finding the mode in Binary Search Tree

algorithm

binary-search-tree

mode