在没有额外 class 的情况下找到二叉树中的最深节点？

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)
    {
        ...
    }
}

有没有其他方法不需要声明新的 class 来规避返回多个值的问题？

Answer 1

具有两个 public 节点和深度字段的 class 是最 Java 做事的方式。备选方案包括：

具有两个元素（节点和深度）的Object[]，并且
A HashMap<String, Object>，其中第一个条目具有键 "node"，其值为节点，第二个条目具有键 "depth"，其值为 Integer代表深度。

一个单独的 class 是最惯用的，对于 Java。其他方式没有 class，但 Java 看起来有点奇怪。例如，Python 和 Java 脚本不需要额外的 class；大多数语言也不会，我猜。 Java 只是坚持名称 -- classes -- 很多。

Answer 2

在更新我之前的回答时，事实证明您可以一次完成此操作。每当你找到一个没有 children 的节点时，当当前深度超过目前找到的最大深度时，保留一个指向它的指针。

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;
}

在没有额外 class 的情况下找到二叉树中的最深节点？

Find Deepest Node in Binary Tree without extra class?

algorithm

binary-tree

data-structures