非递归算叶节点
时间: 2023-07-13 19:05:44 浏览: 50
如果是一棵二叉树,可以使用非递归的方式计算叶节点的数量。具体实现思路如下:
1. 首先将根节点入栈,然后进入循环。
2. 每次从栈中取出一个节点,如果该节点为叶节点,则将计数器加一。
3. 如果该节点有右子树,则将右子树入栈。
4. 如果该节点有左子树,则将左子树入栈。
5. 如果栈为空,则说明所有节点都已经遍历完毕,此时计数器中的值即为叶节点的数量。
以下是具体的代码实现:
```python
def count_leaf_nodes(root):
if root is None:
return 0
stack = [root]
count = 0
while stack:
node = stack.pop()
if node.left is None and node.right is None:
count += 1
if node.right is not None:
stack.append(node.right)
if node.left is not None:
stack.append(node.left)
return count
```
需要注意的是,以上代码中的 `root` 是二叉树的根节点,而 `node.left` 和 `node.right` 分别表示一个节点的左子节点和右子节点。如果是一棵多叉树,可以使用类似的方式进行遍历,只需要将子节点入栈的顺序改为先将右子节点入栈,再将左子节点入栈即可。