java - 查找树中所有叶子的位置(JAVA)

Question

假设我有一棵树，如下所示:

     O
    / \
   O   \
  / \   \
 A   B   C

我如何找到这棵树中所有叶子的位置并将它们输出到数组或 HashMap 中？

所以上面的树将返回:

{{  A   ,     00      },{  B   ,     01      },{  C   ,   1   }}
   leaf    left, left     leaf   left, right     leaf   right

我正在考虑迭代树直到找到一片叶子并记住它走了哪条路。但我不太确定这是否是最有效的方法。

有什么想法可以实现吗？

Answer 1

假设没有可用的现有元数据，最简单的解决方案可能只是常规的深度优先搜索，其中堆栈包含迄今为止所采用的路径。我不知道如何以一种更有效的方式做到这一点。