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

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

答复

您的LeafNodes方法可能返回一个ArrayList<String>. 从空列表开始，添加所有叶节点（n.left），添加所有叶节点（n.right），如果n是叶，则将n添加到列表中。最后，返回列表

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

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

说明：

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

如果它是一个叶，它的值应该写入一个单元素列表，并返回到父节点。这就是你要做的

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

return list

如果节点有子节点，则不应将其值添加到列表中，而应添加一些子节点、孙子节点（或孙子节点或…）必须是leaves，因此它需要将此列表传递给父节点。这就是你要做的：

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

我希望在打电话回来时能说得更清楚