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

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