求所有根节点到叶子节点的二叉树路径完整代码
时间: 2024-03-18 18:15:39 浏览: 14
以下是基于深度优先搜索(DFS)的二叉树路径完整代码,包括二叉树节点的定义、DFS递归函数和主函数:
```python
# 定义二叉树节点
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# DFS递归函数
def dfs(root, path, paths):
# 如果当前节点为空,直接返回
if not root:
return
# 添加当前节点到路径中
path.append(root.val)
# 如果当前节点是叶子节点,将完整路径添加到结果中
if not root.left and not root.right:
paths.append(path[:])
# 递归遍历左子树和右子树
dfs(root.left, path, paths)
dfs(root.right, path, paths)
# 回溯,移除当前节点
path.pop()
# 主函数
def binaryTreePaths(root):
paths = []
dfs(root, [], paths)
return paths
```
主函数`binaryTreePaths`接收根节点作为参数,调用DFS递归函数`dfs`来遍历二叉树并求出所有根节点到叶子节点的路径。`dfs`函数的参数`path`表示当前遍历的路径,`paths`表示所有完整路径的集合。
在`dfs`函数中,首先判断当前节点是否为空,如果为空直接返回。然后将当前节点的值添加到路径中。如果当前节点是叶子节点,将完整路径添加到结果中。接着递归遍历左子树和右子树。最后进行回溯,移除当前节点,恢复路径状态。
最终返回所有完整路径的集合`paths`即可。