Печать всех узлов в K расстояние от корня в двоичное дерево итерационно


Я решить эту интересную задачу кодирования

печать всех узлов в K расстояние от корня бинарного дерева в итеративно

Будет здорово получить отзыв о том, как этот код может быть улучшен в лучшую сторону.

public class NodesAtKDistanceFromRoot {

    private final static Node EMPTY_MARKER = new Node(-1, null, null);

    public static void print(Node root, int level) {

        if (root == null) {
            return;
        }

        Deque<Node> queue = new ArrayDeque<>();
        int d = 1;
        queue.add(root);
        queue.add(EMPTY_MARKER);
        boolean found = false;

        while (!queue.isEmpty()) {

            Node current = queue.remove();

            if (current.equals(EMPTY_MARKER)) {
                // encountered empty marker which means all the nodes of a given level is visited
                d++;
                if (d == level) {
                    found = true;
                    break;
                } else {
                    queue.add(EMPTY_MARKER);
                }
            } else {
                if (current.left != null)
                    queue.add(current.left);

                if (current.right != null)
                    queue.add(current.right);
            }
        }

        // print the nodes for the given level
        if (found) {
            while (!queue.isEmpty()) {
                Node current = queue.remove();
                System.out.println(current.val);
            }
        }
    }

}

Код в GitHub: https://github.com/Ramblers-Code/CodeKata/blob/master/src/main/java/kata/tree/NodesAtKDistanceFromRoot.java



Комментарии
1 ответ

Я думаю, что это достойная реализация. Он читаем и понятен. Тем не менее, у меня есть несколько советов:


  • Старайтесь избегать однобуквенные имена переменных, как d (Если только в очень конкретных случаях, как определенный цикл переменных или математические конструкты).

  • Лично не фанат новой строки после каждой открывающей скобки, он разбивает поток для меня.

  • Старайтесь всегда использовать фигурные скобки с if\while\... заявления. Это поможет предотвратить возможные ошибки.

  • Вы могли бы вместо того, чтобы молча вернуться, бросить (IllegalArgument\Nullpointer)Exception при передаче узла имеет значение null. Не быстро! То же самое с Прошло отрицательных глубинах.

  • Вопрос: как бы вы печатать корень с вашей реализации?

Я тоже не думаю, что тебе нужен маркер. Если вы вместо каждого выполнения цикла только принять все узлы представить в очереди в начале этого цикла, вы будет обрабатывать все уровня узлов на уровне (но только использовать его, если у вас постоянные операции размер времени). В качестве примера:

public static void print(Node root, int depth) {
if (root == null) {
return;
}

Deque<Node> queue = new ArrayDeque<>();
queue.offer(root);

while (!queue.isEmpty()) {
boolean atRequiredDepth = --depth == 0;
int nodeCount = queue.size();

if (atRequiredDepth) {
for (int i = 0; i < nodeCount; i++) {
Node node = queue.poll();
System.out.println(node.val);
}
return;
} else {
for (int i = 0; i < nodeCount; i++) {
Node node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
}
}

1
ответ дан 8 марта 2018 в 08:03 Источник Поделиться