使用非递归方法Java的二叉树的大小

Question

您好，我正在尝试编写一种非递归方法来获取节点的大小，因为Java中的递归非常昂贵。这将包括子节点的数量+
1（自身）。我已经转换了C实现，如何以非递归方式获取二叉树中的叶节点数量？进入Java，但这是不正确的。

编辑：非递归计算二进制树大小的算法。

public int size(Node n) {
    Stack<Node> sizeStack = new Stack();
    int count = 1;//includes the n node
    if(n == null) {
        return 0;
    }
    sizeStack.push(n);
    while(!sizeStack.isEmpty()){
        node = sizeStack.pop();
        while(node != null) {
            count++;
            if(node.right != null){
                sizeStack.push(node.right);
            }
            node = node.left;
        }
    }
    return count;
}

Answer 1

您的算法正在计算 叶节点 。您自己的愿望是计算 所有
节点。对叶节点进行计数的算法仅在弹出叶节点时才添加到计数器，这对于Java和C都是正确的。因此，实际上您的程序是好的-但不适用于您定义的问题。

为了对所有节点进行计数，每次从堆栈中弹出节点时，都必须增加计数器。这意味着您必须推送所有节点，而不是像对待叶节点那样循环。

如果您想节省推送操作（这是为什么该算法比递归更好的唯一原因，除非树向右不平衡），您应该为要检查的每个节点增加计数器，但保持基本循环原样。

public int size(Node n) {
    Stack<Node> sizeStack = new Stack();
    int count = 1;//includes the n node
    if(n == null) {
        return 0;
    }
    sizeStack.push(n);
    while(!sizeStack.isEmpty()){
        node = sizeStack.pop();
        while(node != null) {
            count++;
            if(node.right != null){
                sizeStack.push(node.right);
            }
            node = node.left;
        }
    }
    return count;
}