Найти самый глубокий узел в бинарном дереве без дополнительного класса?

Question

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

Каждое найденное мной решение делает что-то вроде этого:

private class DepthNode
{
    int depth;
    Node n;
}

public class BinaryTree
{
    ...

    public Node deepestNode()
    {
        return deepestNode(root, 0).n;
    }

    private DepthNode deepestNode(Node node, int depth)
    {
        ...
    }
}

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

Answer 1

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

Node deepest_node = null;

void deepestNodeImpl(Node root, int max_depth, int cur_depth) {
  if (!root) return;
  if (!root.left && !root.right) {
    if (cur_depth > max_depth) {
      deepest_node = root;
      max_depth = cur_depth;
    }
    return;
  }
  deepestNodeImpl(root.left, max_depth, cur_depth + 1);
  deepestNodeImpl(root.right, max_depth, cur_depth + 1);
}

Node deepestNode(Node root) {
  deepestNodeImpl(root, -1, 0);
  return deepest_node;
}

Answer 2

Класс с двумя открытыми полями для узла и глубины - это наиболее похожий на Java способ выполнения задач.Альтернативы включают:

• An Object[] с двумя элементами (для узла и глубины) и
• A HashMap<String, Object>, где первая запись имеет ключ "node" и чейзначение - это узел, а вторая запись имеет ключ "depth", значение которого Integer представляет глубину.

Отдельный класс является наиболее идиоматическим для Java.Другие способы не имеют класса, но выглядят немного странно для Java.Например, Python и JavaScript не нуждаются в дополнительном классе;я полагаю, что и большинство языков не работают.Java просто настаивает на именах - и классах - очень много.