0

Есть такой метод, мне кажется что он всегда будет выдавать константное значение, или же он вычисляет ширину дерева? подскажите пожалуйста.

static class Node {
    Node left;
    Node right;

    static int height(Node node) {
        if (node == null) {
            return 0;
        }

        int left = height(node.left);
        int right = height(node.right);
        return Math.max(left, right);
    }
}

1 ответ 1

1

Да, он всегда будет выдавать константное значение, а именно 0. Нужно заменить строчку return Math.max(left, right); на return Math.max(left, right) + 1;. Исправленный вариант:

static class Node {
    Node left;
    Node right;

    static int height(Node node) {
        if (node == null) {
            return 0;
        }

        int left = height(node.left);
        int right = height(node.right);
        return Math.max(left, right) + 1;
    }
}

Хочу заметить, что этот метод вычисляет не ширину дерева, а высоту, то есть расстояние от корня до самого глубокого листа. Если вы хотите вычислять не высоту, а ширину дерева, то сначала стоит определить, что такое ширина дерева. Например, можно определить её как максимальная ширина уровня дерева, где ширина уровня дерева есть число вершин, находящихся на некотором уровне, то есть на одинаковом расстоянии от корня. Тогда алгоритм вычисления ширины дерева выглядит следующим образом:

  1. Найдём глубину дерева уже написанным методом. Обозначим её за h.
  2. Всего уровней в дереве ровно h + 1. Заведём массив на h + 1 элементов, в i-ой его ячейке будет записано число вершин на i-ом уровне. Изначально массив заполнен нулями.
  3. Обойдём дерево любым алгоритмом, в процессе увеличивая соответствующие ячейки массива.
  4. По нашему определению ширина дерева равна максимуму элементов в этом массиве.

Собственно, код:

static class Node {
    Node left;
    Node right;

    static int height(Node node) {
        if (node == null) {
            return 0;
        }

        int left = height(node.left);
        int right = height(node.right);
        return Math.max(left, right) + 1;
    }

    static void dfs(Node node, int nodeHeight, int[] numberVertexesOnLevels) {
        ++numberVertexesOnLevels[nodeHeight];
        dfs(node.left, nodeHeight + 1, numberVertexesOnLevels);
        dfs(node.right, nodeHeight + 1, numberVertexesOnLevels);
    }

    static int width(Node node) {
        int height = height(node);
        int[] numberVertexesOnLevels = new int[height];
        dfs(node, 0, numberVertexesOnLevels);
        return Arrays.stream(numberVertexesOnLevels).max().getAsInt();
    }
}

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.