在二叉树中递归创建叶子列表 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和return中呢。

看看我无望的尝试：

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 函数的 functionality/style 来帮助我编写一个 recursive 函数这将汇总 list 和 return 中所有叶子的数据。

注意：节点的类型是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;
}

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

Creating a list of leaves recursively in a binary tree java

java

recursion

binary-tree