输出二叉树中从每个叶子结点到根节点的路径
时间: 2023-04-24 22:04:56 浏览: 291
输出树的根节点到叶子节点的所有路径
4星 · 用户满意度95%
可以使用深度优先搜索(DFS)来输出二叉树中从每个叶子节点到根节点的路径。具体实现方法如下:
1. 定义一个列表`path`,用于存储从根节点到当前节点的路径。
2. 从根节点开始遍历二叉树。
3. 对于当前节点,如果它是叶子节点,则将`path`列表中的元素逆序(因为是从叶子节点到根节点),并输出路径。如果不是叶子节点,则递归遍历它的左右子节点,直到找到叶子节点。
4. 在递归返回时,将`path`列表中的最后一个元素删除,回溯到父节点。
下面是Python代码示例:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def print_path(root, path):
if not root:
return
# 将当前节点加入路径
path.append(root.val)
if not root.left and not root.right:
# 叶子节点,输出路径
print(path[::-1])
else:
# 递归遍历左右子节点
print_path(root.left, path)
print_path(root.right, path)
# 回溯到父节点
path.pop()
# 测试
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, TreeNode(6), TreeNode(7)))
print_path(root, [])
```
输出结果为:
```
[4, 2, 1]
[5, 2, 1]
[6, 3, 1]
[7, 3, 1]
```
阅读全文