algorithm - 如何在 n 叉树中找到只有叶子的父节点

Question

我正在尝试解决以下算法:

You have an n-ary tree. Find all the nodes satisfying the following condition:

• the node has child node(s) but all of the child nodes are leafs (they have no children ). Return a list of leaf only parent nodes and their depth in the tree.

所以如果我有下面的树，唯一满足上述条件的节点是 D，因为它有后代 (E) 但他们没有 child 。

  I am root!
     /\ \
    A B  F
      /\
     C  D
         \
         E

我正在尝试用 Java 实现它，但伪代码也适用于我。我在这里实现了树和节点结构:N-ary trees in Java .

我只需要算法。

Answer 1

1. 从根开始
2. while left son exists : go to left son
3. 回到父亲那里检查下一个儿子
4. 如果没有其他儿子:将父亲插入列表
5. 否则将父亲插入列表并转到第 2 步，但保留深度计数器，如果找到孙子:从列表中删除父亲

6. 如果完成所有节点:返回列表

   根/\\A B F/\CD \ E

运行示例:

• 去A
• 返回根目录并将根目录插入列表
• 去B
• 转到C(由于计数器而从潜在中删除根)
• 返回 B 并将 B 添加到列表中
• 去D
• 转到 E(由于计数器而将 B 从潜力中移除)
• 回到D并插入列表
• 回到B
• 回到根目录
• 转到 F(不要插入 root，因为 root 已经插入 [并删除]
• 返回只有D的列表

要完成这项工作，您应该为正在检查的节点运行一个计数器(以查看是否存在孙节点)，并且您还应该有一种方法知道节点是否已从列表中删除，以便您不会插入它再次(我没有明确地写它，但我使用了 2 个列表 - 1 个用于潜力，1 个用于最终)