如何找到我試圖解決以下算法N叉樹

有N叉樹。查找滿足以下條件的所有節點：

節點有子節點（或多個），但子節點的所有是葉子（他們沒有孩子）。返回樹中只有葉節點的父節點列表和它們的深度。

所以，如果我有下面的樹，滿足上述條件的唯一節點是d，因爲它的後代（E），但他們沒有孩子。

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

我想在Java中實現這一點，但僞代碼也適用於我。我有這裏實現的樹和節點結構：N-ary trees in Java。

我需要的只是算法。

來源

2016-12-25 Boyko Arsov

在根開始
而左兒子存在：向左走兒子
回到父親和檢查下一個兒子
，如果沒有其他的兒子：插入父親列出
其他插入父親列出並進入第2步，但保留深度計數器，如果發現孫輩：從列表中刪除父親
如果完成所有節點：返回列表

根 /\ \ ABF /\ CD \ Ë

運行例如：

去
回去根插根列出
轉到B
轉到C（刪除根目錄從因爲計數器的潛力）
回到B和B加入A列出
去d
去E（從因爲計數器的潛力）除去乙
回去d，並插入到列表
回去到B
回去根
去F（不插根，因爲根已插入[和刪除]
它只有d返回列表

爲了使這項工作，你應該有一個計數器運行你正在檢查的節點（看孫兒們是否存在），並且你應該有一種方法來知道節點是否已經從列表中刪除，所以你不會再次插入它（我沒有明確地寫它，但我用2列表 - 1的潛力和1最後）

來源

2016-12-25 12:32:27 CIsForCookies

好吧，我明白了。這是我已經達到的解決方案。我相信雖然有更好的解決方案 - 歡迎您糾正我。

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

來源

2016-12-25 13:34:17

如何找到我試圖解決以下算法N叉樹

回答

相關問題