求二叉树中从根结点到叶子结点的路径
时间: 2023-12-29 11:04:04 浏览: 64
数据结构大作业求二叉树上结点的路径.zip
5星 · 资源好评率100%
二叉树中从根节点到叶子节点的路径可以通过深度优先搜索(DFS)来实现。具体步骤如下:
1. 从根节点开始,将根节点加入到路径中。
2. 若当前节点是叶子节点,则输出当前路径。
3. 若当前节点不是叶子节点,则遍历其左子树和右子树,并将左右子树的结果合并。
4. 在返回到当前节点的父节点时,将当前节点从路径中删除。
下面是一个 Python 实现:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def binaryTreePaths(self, root: TreeNode) -> List[str]:
if not root:
return []
res = []
def dfs(node, path):
if not node.left and not node.right:
res.append('->'.join(path))
return
if node.left:
dfs(node.left, path + [str(node.left.val)])
if node.right:
dfs(node.right, path + [str(node.right.val)])
dfs(root, [str(root.val)])
return res
```
在这个实现中,我们使用了递归的方式来遍历二叉树,并将遍历的路径保存在一个列表中。最后,我们将每个路径连接起来并返回结果。
阅读全文