Как найти глубину дерева итеративно в Java?

Question

В одном из интервью меня попросили найти глубину дерева. Я сделал это рекурсивно, но потом интервьюер попросил меня сделать это с помощью итерации. Я сделал все возможное, но я не думаю, что он выглядел вполне убежденным. Может кто-нибудь написать псевдокод здесь или код будет предпочтительнее ... Спасибо за чтение сообщения.

Answer 1

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

Answer 2

Tree<Object> tree = ...; // source

class NodeMarker {
    public NodeMarker(TreeNode node, int depth) { ... }
    public TreeNode node;
    public int depth;
}

int depth = 0;
List<NodeMarker> stack = new LinkedList<NodeMarker>();
for (TreeNode node : tree.getChildren())
    stack.add(new NodeMarker(node, 1);

while (stack.size() > 1) {
    NodeMarker marker = stack.get(0);
    if (depth < marker.depth)
        depth = marker.depth;

    if (marker.node.hasChildren())
        for (TreeNode node : marker.node.getChildren())
            stack.add(new NodeMarker(node, marker.depth + 1);
}

Answer 3

Итерация, а не рекурсия означает, что вы идете по дереву, вместо того, чтобы каждый вызов функции порождал два новых вызова функции, вы можете хранить каждый элемент слоя в массиве.Попробуйте начать с (одного элемента) массива, содержащего указатель на корень.Затем в цикле (я бы просто использовал while (1)) итерацию по этому массиву (currentLayer), создание нового массива (nextLayer) и добавление дочерних элементов каждого элемента currentLayer в nextLayer.Если следующий слой пуст, вы находитесь на самом глубоком слое, в противном случае увеличьте глубину на единицу, скопируйте nextLayer в currentLayer и сделайте это снова.