Рекурсивно подсчитывать количество листьев в двоичном дереве без заданных параметров

Question

Я пытаюсь выяснить, как закодировать рекурсивный алгоритм для подсчета количества листьев в двоичном дереве (не полное дерево). Я добираюсь до самого левого листа и не знаю, что вернуться оттуда. Я пытаюсь получить счет, загружая листья в список и получая размер этого списка. Вероятно, это плохой способ подсчета.

public int countLeaves () { 

    List< Node<E> > leafList = new ArrayList< Node<E> >(); 
    //BinaryTree<Node<E>> treeList = new BinaryTree(root); 

    if(root.left != null) 
    { 
     root = root.left; 
     countLeaves(); 
    } 
    if(root.right != null) 
    { 
     root = root.right; 
     countLeaves(); 
    } 
    if(root.left == null && root.right == null) 
    { 
     leafList.add(root); 
    } 


     return(); 
} 

Answer 1

развивавших по идее @dasblinkenlight. Вы хотите, чтобы рекурсивно вызывать подсчеты на корневом узле &, передать номер # вызывающему. Что-то в следующих строках.

public int countLeaves() { 
return countLeaves(root); 
} 

/** 
* Recursively count all nodes 
*/ 
private static int countLeaves (Node<E> node) { 
if(node==null) 
    return 0; 

if(node.left ==null && node.right == null) 
    return 1; 
else { 
    return countLeaves(node.left) + countLeaves(node.right); 
    } 
} 

Edit: Похоже, подобная проблема была ранее попросила counting number of leaf nodes in binary tree

Answer 2

Проблема с реализацией в том, что она не восстанавливает значение переменной-члена root обратно в состояние, которое он имел перед входом в метод. Вы можете сделать это путем сохранения значения в локальной переменной, т.е.

Node<E> oldRoot = root; 
... // your method goes here 
root = oldRoot; 

Однако лучший подход заключается в Node<E> в качестве аргумента, а не полагаться на общей переменной:

public int countLeaves() { 
    return countLeaves(root); 
} 

private static int countLeaves (Node<E> node) { 
    ... // Do counting here 
}