非递归求二叉树的叶结点个数
时间: 2024-01-22 12:18:53 浏览: 107
求二叉树中叶子结点的数目
非递归求二叉树的叶结点个数可以通过栈来实现。具体步骤如下:
1. 定义一个栈,并将根节点压入栈中。
2. 当栈不为空时,弹出栈顶元素,如果该元素是叶子节点,则计数器加1。
3. 如果该元素不是叶子节点,则将其右子节点和左子节点(如果存在)依次压入栈中。
4. 重复执行第2步到第3步,直到栈为空。
以下是该算法的Python代码实现:
```python
def count_leaves(root):
if not root:
return 0
count = 0
stack = [root]
while stack:
node = stack.pop()
if not node.left and not node.right:
count += 1
else:
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return count
```
其中,root是二叉树的根节点,该函数返回二叉树的叶子节点个数。
阅读全文