用遞歸方法收集二叉樹中葉節點的值

Question

我必須爲學校任務創建一個二叉搜索樹的類，而且我必須實現的方法之一是要返回一個全部葉節點值用逗號分隔，如[「葉節點1」，葉節點2，葉節點3]。 從左到右。

我必須解決這個使用遞歸方法幫扶，我完全空白

這是我迄今爲止

public void leafNodes(Node<T> n) 
{ 
    if(n.left != null) leafNodes(n.left); 
    if(n.right != null) leafNodes(n.right); 

    if(n.left == null && n.right == null) 
    { 
     // Do something in here? 
    } 
} 

建議後

嘗試編輯：

I tried adding it like this: 

public ArrayList<String> leafNodes(Node<T> n) 
{ 
    ArrayList<String> list = new ArrayList<>(); 

    if(n.left != null) leafNoder(n.left); 
    if(n.right != null) leafNoder(n.right); 

    if(n.left == null && n.roight == null) 
    { 
     list.add(n.value.toString()); 
    } 
    return list; 
} 

現在使用此幫助方法的方法返回一個空字符串。或者只是「[]」。

public String LeafNodeValues() 
{ 
    StringJoiner sj = new StringJoiner(", ", "[","]"); 

    if(empty()) return sj.toString(); 

    ArrayList<String> a = leafNodes(rot); 

    for(int i = 0; i < a.size(); i++) 
    { 
     sj.add(a.get(i)); 
    } 
    return sj.toString(); 
} 

是這樣的？

public ArrayList<String> leafNodes(Node<T> n) 
{ 
ArrayList<String> list = new ArrayList<>(); 

if(n.left != null) list.addAll(leafNoder(n.left)); 
if(n.right != null) list.addAll(leafNoder(n.right)); 

if(n.left == null && n.roight == null) 
{ 
    list.add(n.value.toString()); 
} 
return list; 

}

Answer 1

回答

你的葉節點方法可能會返回一個ArrayList<String>. 你開始與空List，你中的addAll葉節點（n.left），你中的addAll葉節點（n.right）如果n是葉子，則將n添加到列表中。最後，你返回列表。

要獲得期望的結果，你可以調用根節點葉節點，並使用：

String.join(",", leafNodes(root)); 

說明：

在你的二叉樹，每個節點有0子（葉）， 1名兒童或2名兒童。

如果它是一個葉子，它的值應該寫入一個元素列表中，並返回到父節點。這是你與

list.add(n.value.toString());

return list

如果節點有孩子，它的價值不應該被添加到列表中做什麼，但有些孩子，孫子（或grandgrandchildren或...）必須是離開，所以它需要將這個列表傳遞給父節點。這是你做什麼：

list.addAll(leafNodes(n.left));

list.addAll(leafNoder(n.left));

return list

例

下面是一個例子與二叉樹只有6個節點：

1 
2 
    4 
    5 
3 
    6 

和一些調試信息：

calling leafNodes(1) 
calling leafNodes(2) 
    calling leafNodes(4) 
    4 is a leaf 
    returning [4] for 4 
    calling leafNodes(5) 
    5 is a leaf 
    returning [5] for 5 
    returning [4, 5] for 2 
calling leafNodes(3) 
    calling leafNodes(6) 
    6 is a leaf 
    returning [6] for 6 
    returning [6] for 3 
returning [4, 5, 6] for 1 

我希望它在調用和返回時更清晰。