数据结构-二叉树（求二叉树叶子节点数的递归和非递归算法）

思路

思路这一块没啥可说，递归主要是求左子树叶子结点数+求右子树叶子结点数，递归实现。非递归就是用到了栈，一个结点一个结点的保存，保存到叶子结点时候，就让叶子出栈，计数+1，然后让栈顶指向右结点再入栈循环执行即可

Java 实现

// 结点
class Node {
    int data;
    Node left = null;
    Node right = null;
}

// 二叉树
public class BinaryTree {
    // 根结点
    private Node root;
    // 输入的数组
    private int[] arr_in;
    // 输出的数组
    private int[] arr_out;
    // 记录数组下标
    private static int index;

// 得到二叉树叶子结点的个数（递归）
    public int getLeafCountRecursion(Node r) {
        if (r.left == null && r.right == null)
            return 1;
        else
        	return getLeafCountRecursion(r.left) + getLeafCountRecursion(r.right);
    }
    
    // 得到二叉树叶子结点的个数（非递归）
    public int getLeafCount(Node r) {
        Stack stack = new Stack();
        Node node = r;
        int count = 0;
        while (r || !stack.empty()) {
            if (r.left != null || r.right != null) {
                stack.push(node);
                node = r.left;
            }
            else {
                count++;
                node = stack.pop().right;
            }
            
        }
    }