求二叉树上结点的路径
时间: 2024-02-25 18:58:09 浏览: 78
要求二叉树上结点的路径,可以使用深度优先搜索(DFS)算法进行求解。具体步骤如下:
1. 从根节点开始进行DFS遍历,遍历过程中记录当前路径。
2. 遍历到目标结点时,将当前路径保存下来。
3. 继续DFS遍历,直到遍历完整棵树。
4. 返回所有保存的路径,即为所有结点到目标结点的路径。
以下是一个示例代码,假设要求从根节点到目标结点的路径:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def find_path(root, target):
res = []
path = []
dfs(root, target, path, res)
return res
def dfs(node, target, path, res):
if not node:
return
path.append(node)
if node == target:
res.append([p.val for p in path])
dfs(node.left, target, path, res)
dfs(node.right, target, path, res)
path.pop()
```
在这个示例代码中,`find_path` 函数接收根节点和目标结点作为参数,返回所有结点到目标结点的路径。`dfs` 函数是主要的DFS遍历函数,接收当前节点、目标结点、当前路径和结果列表作为参数。
在遍历过程中,将当前节点添加到路径中。如果当前节点是目标结点,将当前路径保存到结果列表中。继续递归遍历左右子树,并在遍历完左右子树后将当前节点从路径中弹出,以便进行下一个遍历。
阅读全文
相关推荐











