输出二叉树中从每个叶子结点到根结点的路径
时间: 2023-12-29 21:04:05 浏览: 72
数据结构大作业求二叉树上结点的路径.zip
5星 · 资源好评率100%
以下是输出二叉树中从每个叶子结点到根结点的路径的 Python 代码:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def print_all_paths(root: TreeNode):
def dfs(node, path):
if not node:
return
path.append(node.val)
if not node.left and not node.right:
print(path[::-1])
else:
dfs(node.left, path)
dfs(node.right, path)
path.pop()
dfs(root, [])
```
这里我们使用深度优先搜索(DFS)遍历整个二叉树,并用一个列表 `path` 记录当前遍历路径上经过的结点值。当遇到叶子结点时,我们将 `path` 列表反转输出,即得到从叶子结点到根结点的路径。
注意在每次遍历完一个结点后,需要将其从 `path` 列表中弹出,以确保下一次遍历从正确的位置开始。
阅读全文