求二叉树上结点的路径程序设计
时间: 2024-03-16 19:41:06 浏览: 29
二叉树上结点的路径可以通过递归遍历二叉树实现。具体的程序设计如下:
```python
# 定义二叉树结点
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# 递归遍历二叉树,查找目标结点
def findPath(root, target, path):
if not root:
return False
# 将当前结点加入路径
path.append(root.val)
# 如果当前结点就是目标结点,则返回 True,表示找到了目标结点
if root.val == target:
return True
# 在左子树中查找目标结点
if root.left and findPath(root.left, target, path):
return True
# 在右子树中查找目标结点
if root.right and findPath(root.right, target, path):
return True
# 如果左右子树都未找到目标结点,则将当前结点从路径中删除
path.pop()
return False
# 主函数,查找二叉树根节点到目标结点的路径
def getPath(root, target):
path = []
findPath(root, target, path)
return path
```
调用 `getPath` 函数即可得到二叉树根节点到目标结点的路径。例如,对于下面的二叉树:
```
1
/ \
2 3
/ \
4 5
```
如果要查找结点值为 5 的结点,可以这样调用函数:
```python
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
path = getPath(root, 5)
print(path) # 输出 [1, 2, 5]
```
这样,就可以得到从根节点到结点值为 5 的结点的路径 [1, 2, 5]。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)