java - 在二叉树java中递归创建叶子列表

Question

我计算二叉树中叶子数量的递归函数工作正常:

public static int numberOfLeaves(BinaryTree<String> root) {

    if (root == null) return 0;
    else if(root.isLeaf()) return 1;
    int left = numberOfLeaves(root.leftTree);
    int right = numberOfLeaves(root.rightTree);
    return (left + right);
}

但是现在我想对 List 中所有叶子的数据求和并归还它。

看看我无望的尝试:

public ArrayList<String> getDataLeaves(BinaryTree<String> root) {

    ArrayList<String> list = new ArrayList<>();

    if (root == null) return list;
    else if (root.isLeaf()) list.add(root.data);
    else if(root.leftTree != null ) getDataLeaves(root.leftTree);
    else getDataLeaves(root.rightTree);

    return list;
}

我可以(如何)使用我的 numberOfLeaves 函数的功能/风格来帮助我编写一个递归函数来汇总所有叶子的数据在列表中并返回它。

注意: 节点的类型为 BinaryTree<String> 与 data , leftTree , RightTree作为实例变量。

Answer 1

您应该添加递归调用返回的叶子:

public ArrayList<String> getDataLeaves(BinaryTree<String> root) {

    ArrayList<String> list = new ArrayList<>();

    if (root == null) 
        return list;
    else if (root.isLeaf()) 
        list.add(root.data);
    else { 
        list.addAll(getDataLeaves(root.leftTree));
        list.addAll(getDataLeaves(root.rightTree));
    }

    return list;
}