在二叉树中找到最深的节点而不需要额外的类?

对于节点和深度有两个公共字段的类是最像Java的方法。备选方案包括:

• 安 Object[]
• A HashMap<String, Object> 其中第一个条目有密钥 "node" 其值是节点,第二个条目具有键 "depth" 它的价值是 Integer 代表深度。

但是对于Java来说,一个单独的类是最惯用的。其他方法没有类,但是对于Java来说有点奇怪。例如,Python和JavaScript不需要额外的类;我猜,大多数语言也一样。Java非常强调名称和类。

在更新我以前的答案,原来你可以做到这一点,在一个通过。每当您找到一个没有子节点的节点时,当当前深度超过到目前为止找到的最大深度时,请保留一个指向该节点的指针。

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