访问二叉树的叶子结点

方法一：递归前序遍历

当我们想要二叉树的叶子节点时，我们可以采用递归前序遍历的方式。这种方式就像我们深入每一层级的节点，亲自检查每一个节点是否为叶子节点。代码示例如下：

```python

class TreeNode:

def __init__(self, val=0, left=None, right=None):

self.val = val

self.left = left

self.right = right

def traverse_and_find_leaves_recursively(root):

leaf_nodes = [] 用于存储叶子节点的列表

def helper(node): 辅助函数，进行递归遍历

if node is None: 如果节点为空，直接返回

return

if node.left is None and node.right is None: 如果节点是叶子节点

leaf_nodes.append(node.val) 将该叶子节点添加到列表中

helper(node.left) 递归遍历左子树

helper(node.right) 递归遍历右子树

helper(root) 从根节点开始遍历

return leaf_nodes 返回叶子节点的列表

```

方法二：迭代前序遍历

除了递归，我们还可以使用迭代的方式模拟前序遍历，利用栈来存储待处理的节点。代码示例如下：

```python

def iterate_and_find_leaves(root):

if not root: 如果树为空，直接返回空列表

return []

stack = [root] 将根节点放入栈中

leaf_nodes = [] 用于存储叶子节点的列表

while stack: 当栈不为空时，继续处理节点

node = stack.pop() 弹出栈顶节点进行处理

if node.left is None and node.right is None: 如果节点是叶子节点

leaf_nodes.append(node.val) 将该叶子节点添加到列表中

if node.right: 先将右子节点入栈，确保左子树先被处理（满足前序遍历顺序）

stack.append(node.right)

if node.left: 再将左子节点入栈

stack.append(node.left) 因为栈是后进先出的，所以先入栈的左子节点会被后处理

return leaf_nodes 返回叶子节点的列表

```

方法三：层次遍历（广度优先搜索） 层次遍历是一种逐层访问二叉树节点的方法。我们使用队列来按层存放待处理的节点。代码示例如下： 层次遍历可以确保按照树的层级结构顺序访问每一个节点，包括叶子节点。 ```python from collections import deque def bfs_find_leaves(root): if not root: return [] queue = deque([root]) 使用双端队列来模拟队列操作 leaf_nodes = [] while queue: node = queue.popleft() 从队列的左侧弹出一个节点进行处理 if node.left is None and node.right is None: 如果该节点是叶子节点 leaf_nodes.append(node.val) 将该叶子节点的值添加到列表中 else: 如果该节点不是叶子节点 if node.left: 将左子节点加入队列 queue.append(node.left) if node.right: 将右子节点加入队列 queue.append(node.right) return leaf_nodes 返回包含所有叶子节点值的列表 解释 递归前序遍历：先处理当前节点（包括判断是否为叶子节点），再递归处理左右子树。迭代前序遍历：利用栈模拟递归过程，确保节点的处理顺序符合前序遍历的要求。层次遍历（广度优先搜索）：按照树的层级结构逐层访问节点，包括叶子节点。这些方法在时间和空间复杂度上相似，可以根据具体需求和场景选择合适的方法。 ``` 以上三种方法都是用来访问二叉树的叶子节点的有效手段。它们各有特点，可以根据实际情况选择使用。