写出代码 要求输出二叉树中从每个叶子节点到根节点的路径。(二叉链表作为存储结构)
时间: 2024-12-19 16:23:31 浏览: 13
在Python中,我们可以使用递归的方式来遍历二叉树并记录从每个叶子节点到根节点的路径。这里假设二叉链表节点包含左孩子、右孩子和值三个属性。下面是一个简单的示例代码:
```python
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def get_leaf_paths(root):
paths = []
_get_leaf_paths(root, [], paths)
return paths
def _get_leaf_paths(node, path, paths):
if node is None:
return
path.append(node.value)
if node.left is None and node.right is None: # 判断是否是叶子节点
paths.append(list(path)) # 把当前路径添加到结果列表中
else:
_get_leaf_paths(node.left, path.copy(), paths) # 递归处理左子树
_get_leaf_paths(node.right, path.copy(), paths) # 递归处理右子树
path.pop() # 回溯,移除最后一个节点,准备处理下一个子节点
# 使用示例
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
paths = get_leaf_paths(root)
for path in paths:
print(path)
```
在这个例子中,`get_leaf_paths`函数会返回所有叶子节点到根节点的路径列表,每个路径都是一个整数列表。
阅读全文