如何在n元树中查找仅叶的父节点

Question

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

您有一棵n元树。找到满足以下条件的所有节点：

< li >该节点有子节点，但所有子节点都是叶节点(它们没有子节点)。返回仅叶父节点的列表及其在树中的深度。

因此，如果我有下面的树，唯一满足上述条件的节点是D，因为它有子节点（E），但它们没有子节点。

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

我试图在Java中实现这一点，但伪代码也适用于我。我在这里实现了树和节点结构：Java中的N元树。

我需要的只是算法。

Answer 1

好的，我知道了。这是我得出的解决方案。我确信有更好的解决方案，欢迎你来纠正我。

// kick off the recursion
public Map<Integer, Integer> findLeafOnlyParents(GenericTree<Integer> tree){
        Map<Integer, Integer> resultMap = new HashMap<>();

    // start search from the root
        traverseWithDepth(tree.getRoot(), resultMap, 0);

        return resultMap;
    } 


private void traverseWithDepth(GenericTreeNode<Integer> node,  Map<Integer, Integer> traversalResult, int depth) {

  // check if the current note in the traversal is parent Of leaf-only nodes
  if (isParentOfLeafOnly(node)){
    traversalResult.put(node.data, depth);
  }

  // check the node's children
  for(GenericTreeNode<Integer> child : node.getChildren()) {
    traverseWithDepth(child, traversalResult, depth + 1);
  }

}

// the main logic is here
private boolean isParentOfLeafOnly(GenericTreeNode<Integer> node){
  boolean isParentOfLeafOnly = false;

  // check if the node has children
  if(node.getChildren().size() > 0){

    // check the children of the node - they should not have children
    List<GenericTreeNode<Integer>> children = node.getChildren();
    boolean grandChildrenExist = false; 

    // for each child check if it has children of its own
    for(GenericTreeNode<Integer> child : children) {
      grandChildrenExist = child.getChildren().size() > 0;

      // once found note that the current node has grandchildren,
      // so we don't need to check the rest of the children of the node
      if (grandChildrenExist){
        break;
      }
     }

     // we need only the parents who don't have great children
    isParentOfLeafOnly = !grandChildrenExist;
  }
  return isParentOfLeafOnly;
}

Answer 2

>

从根开始

左子存在时：转到左子

回到父亲身边，检查下一个儿子。

如果没有其他儿子：在列表中插入父亲

否则，将父亲插入列表并转到步骤2，但保留深度计数器，如果找到孙子：从列表中删除父亲

如果完成所有节点：返回列表

root / \ \ A B F / \ C D \ E

运行示例:

• 转到 A
• 返回根目录并将根目录插入列表
• 转到 B
• 转到 C（由于计数器而从电位中删除根）
• 返回 B 并将 B 添加到列表
• 转到 D
• 转到 E（由于计数器而从电位中删除 B）
• 返回 D 并插入到列表
• 返回 B
• 返回根目录
• 转到 F（不要插入根，因为根已经插入 [并删除]
• 返回只有 D 的列表

要使这项工作，你应该为你正在检查的节点运行一个计数器（看看孙子是否存在），并且你也应该有一种方法来知道一个节点是否已经从列表中删除，这样你就不会再插入它了（我没有明确地写它，但我使用了2个列表 - 1个用于潜力，1个用于最终）