具有非递归方法Java的二叉树的大小

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

编辑：用于计算二叉树大小的算法，非递归。

public int size(Node n) { Stack 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 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 2

这是一个C实现。 上面的RealSkeptic方法对我来说并不那么直观。 我提供评论，应该很容易理解。

 int sizeOfBsTree_nonRec(TreeNode *root) { if (root == NULL) { return 0; } int size = 0; Stack S; initializeStack(&S); // Push to the stack all Nodes in the (sub)tree and // increase the counter when you pop one out push(root, &S); while(!isStackEmpty(&S)){ root = pop(&S); size++; if (root->right != NULL) push(root->right, &S); if (root->left != NULL) push(root->left, &S); } return size; }