Создание списка листьев рекурсивно в двоичном дереве 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 , чтобы помочь мне написать рекурсивная функция, которая будет суммировать данные всех листьев в списке и возвращать it.

Примечание: узел имеет тип 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;
}