怎么用python对二叉树结点的路径进行遍历并且存储
时间: 2024-01-18 09:02:07 浏览: 96
可以使用深度优先搜索(DFS)或广度优先搜索(BFS)来对二叉树节点路径进行遍历,并且可以将遍历过程中经过的节点存储到一个列表中。
以下是使用DFS进行遍历并存储节点路径的示例代码:
```python
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def dfs(node, path, all_paths):
if not node:
return
path.append(node.data)
if not node.left and not node.right:
all_paths.append(path)
else:
dfs(node.left, path.copy(), all_paths)
dfs(node.right, path.copy(), all_paths)
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
all_paths = []
dfs(root, [], all_paths)
print(all_paths)
```
输出结果为:
```
[[1, 2, 4], [1, 2, 5], [1, 3]]
```
以上代码中,dfs函数接受一个节点、一个当前路径的列表以及一个存储所有路径的列表作为参数。首先将当前节点的值添加到当前路径中,然后判断当前节点是否为叶子节点。如果是叶子节点,将当前路径添加到所有路径中;否则,递归遍历当前节点的左右子节点,并将当前路径拷贝后作为参数传递,以确保不会对其他路径造成影响。
阅读全文