用递归和非递归求叶子数
时间: 2024-02-12 20:05:50 浏览: 29
好的,这是一个关于树的问题。以下是两种方法:
1. 递归方法:
在树的递归遍历中,当遍历到一个叶子节点时,叶子数加1。具体实现代码如下:
```python
def count_leaves_recursive(node):
if not node:
return 0
if not node.left and not node.right:
return 1
return count_leaves_recursive(node.left) + count_leaves_recursive(node.right)
```
2. 非递归方法:
非递归方法需要使用栈来模拟递归过程。从根节点开始,将根节点入栈。在循环中,每次从栈中取出一个节点,如果该节点是叶子节点,则叶子数加1。否则,将该节点的左右子节点入栈。具体实现代码如下:
```python
def count_leaves_iterative(root):
if not root:
return 0
stack = [root]
count = 0
while stack:
node = stack.pop()
if not node.left and not node.right:
count += 1
else:
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return count
```
希望这两种方法能够帮助到你!
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)