Определите самый высокий уровень, который является полным - бинарное дерево поиска - PullRequest
Новая
       7

Определите самый высокий уровень, который является полным - бинарное дерево поиска

0 голосов
/ 19 ноября 2018

У меня есть проект, и у меня есть все, кроме того, где мне нужно найти самый высокий уровень с максимальным количеством узлов в нем.Это код, который у меня есть, но я не могу понять, как это сделать: 

 public int fullLevel() {
    int height = 1;
    int count = 1;
    fullLevel(root, height, count);
    return height;
} 

private int fullLevel(Node temp, int height, int count) {
    int height2 = (int) Math.pow(2, height - 1);

    if (temp == null) {
        return 0;
    }
    if (count == height2 && temp.left != null && temp.right != null) {
        count = 0;
        return fullLevel(temp.right, count, height + 1) + fullLevel(temp.left, count, height + 1);
    } else if (count != height2) {
        return fullLevel(temp.right, count + 1, height) + fullLevel(temp.left, count + 1, height);
    } else {
        return height;
    }
}

Вопрос задает вопрос: «Определите самый высокий уровень, который заполнен, или, что эквивалентно, имеетмаксимальное количество узлов для этого уровня. "- Нужно использовать рекурсию.Спасибо!

Я не очень хорош в рекурсии, поэтому заранее извините!

1 Ответ

0 голосов
/ 19 ноября 2018

Вы на правильном пути, сравнивая количество реальных детей на каждом уровне с количеством возможных детей для этого уровня. Идеальным подходом было бы выполнить обход уровня порядка, используя очередь, и вернуть самый высокий полный уровень. Однако, поскольку вы застряли с помощью рекурсии, проблема становится в том, чтобы поддерживать счет по горизонтали между рекурсивными вызовами. Наивным решением является создание списка отсчетов для каждой высоты, а затем возврат последнего полного уровня в этом списке.

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

public static int fullLevel(Node root) {
    ArrayList<Integer> levelCounts = new ArrayList<>();
    levelCount(root, 0, levelCounts);

    for (int i = levelCounts.size() - 1; i >= 0; i--) {
        if ((int)Math.pow(2, i) == levelCounts.get(i)) {
            return i;
        }
    }

    return -1;
}

private static void levelCount(Node root, int height, ArrayList<Integer> levelCounts) {
    if (root != null) {
        if (height >= levelCounts.size()) {
            levelCounts.add(0);
        }

        levelCounts.set(height, levelCounts.get(height) + 1);

        if (root.left != null && root.right != null) {
            levelCount(root.left, height + 1, levelCounts);
            levelCount(root.right, height + 1, levelCounts);
        }
    }
}

Вывод равен 2 (с нулями) для следующего дерева примеров: 

       ____1____
      /         \ 
    _2_        __3__
   /   \      /     \
  4     5    6      _7_    <-- tallest full level
 / \   /    / \    /   \
8   9 10   11  12 13   14

Попробуйте!

...