用递归算法实现输出二叉树中从每个叶子结点到根结点的路径
时间: 2024-01-22 17:20:05 浏览: 23
以下是递归算法实现输出二叉树中从每个叶子结点到根结点的路径的示例代码(假设二叉树的节点结构为 TreeNode,包含 val、left 和 right 三个成员变量):
```python
def print_paths(root):
if not root:
return
paths = []
find_paths(root, [], paths)
for path in paths:
print(' -> '.join([str(val) for val in path[::-1]]))
def find_paths(node, path, paths):
if not node:
return
path.append(node.val)
if not node.left and not node.right:
paths.append(path)
else:
find_paths(node.left, path[:], paths)
find_paths(node.right, path[:], paths)
```
在主函数中,我们首先调用 find_paths 函数,该函数用于递归遍历二叉树,查找从当前节点到叶子结点的所有路径。在该函数的实现中,我们使用 path 列表来存储当前节点到根节点的路径,如果当前节点是叶子结点,则将该路径添加到 paths 列表中。否则,我们分别递归遍历节点的左右子树,并将当前路径的副本传递给每个递归调用,以避免在不同的递归调用之间共享相同的路径。
最后,在 print_paths 函数中,我们遍历所有从叶子结点到根节点的路径,并将其转换为字符串形式并输出。需要注意的是,在输出路径时,我们将路径列表倒序排列,以便将根节点放在最后一个位置。