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

Question

我必须使用递归帮助方法来解决这个问题，而我完全是空白的

这是我目前所掌握的

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

LeafNodes方法可以返回ArrayList 。 以空列表开头，添加All LeafNodes(n.left)，添加All LeafNodes(n.right)，如果n是leaf，则将n添加到列表中。最后，您返回列表。

要获得所需的结果，您可以在根节点上调用leafNodes，并使用：

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

在你的二叉树中，每个节点都有0个子（一个叶子）、1个子或2个子。

List.AddAll（leafNodes（n.left））；

List.AddAll（leafNoder（左））；

返回列表

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