用递归方法收集二叉树中叶节点的值

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 

我希望它在调用和返回时更清晰。