Блог

Я видел, что этот вопрос обсуждался на этом сайте, но я хотел бы обсудить один вопрос, пожалуйста, об отслеживании prev значения в приведенном ниже коде. Приведено следующее решение для поиска режима в двоичном дереве поиска,

 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 resu<

    }
    //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 должна захватить предыдущее значение узла, чтобы, когда мы войдем в левый дочерний элемент узла, как показано в коде, мы немедленно сравним его с левым дочерним элементом этого узла. Например, если prev = 5 , как только мы дойдем до 10, появится новое предыдущее prev = root.val; число , то мы получим 15 правильных детей из 10. Но мы сравниваем prev не с 15, а с 10, так как мы сразу же идем влево в коде один раз, поэтому мы сравниваем prev = 10 с node.val в if(prev == root.val) строке. Оттуда мы перейдем ко всем остальным узлам.

Проблема: Предположим , что узел, который сразу же оставлен 30 , есть 25 и нет 20 , тогда трюк, используемый в этом решении, в этом случае не сработает, как вы думаете, пожалуйста?

Алгоритм выполняет обход дерева по порядку, что делает это:

1. пересечение левого поддерева путем рекурсивного вызова функции по порядку.
2. получите доступ к части данных текущего узла.
3. пройдите по правому поддереву, рекурсивно вызвав функцию по порядку.

В двоичном дереве поиска из-за порядка узлов обход по порядку посещает узлы в порядке возрастания, отсортированном по возрастанию.

Я думаю, что эта фотография (любезно предоставленная Википедией) поможет объяснить, что происходит:

Обход по порядку будет посещать узлы в этом порядке:

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.