设计一程序求二叉树上结点的路径。
时间: 2024-05-05 08:20:00 浏览: 61
好的,以下是求二叉树上结点路径的程序:
```python
# 定义二叉树结点类
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# 递归函数,用于求从根节点到目标结点的路径
def findPath(root, target):
if not root:
return []
# 如果当前结点是目标结点,直接返回该结点
if root.val == target:
return [target]
# 在左子树中查找目标结点
left_path = findPath(root.left, target)
# 在右子树中查找目标结点
right_path = findPath(root.right, target)
# 如果目标结点在左子树中,则将当前结点加入到路径中并返回
if left_path:
return [root.val] + left_path
# 如果目标结点在右子树中,则将当前结点加入到路径中并返回
if right_path:
return [root.val] + right_path
# 如果目标结点既不在左子树中,也不在右子树中,则说明目标结点不存在于当前子树中,返回空列表
return []
# 测试代码
if __name__ == '__main__':
# 构造二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
# 求结点4的路径
print(findPath(root, 4)) # 输出[1, 2, 4]
# 求结点7的路径
print(findPath(root, 7)) # 输出[1, 3, 7]
```
这个程序使用了递归的思想,对于每个结点,首先判断该结点是否是目标结点,如果是,直接返回该结点;如果不是,则在其左子树和右子树中查找目标结点,如果在左子树中找到了目标结点,则将当前结点加入到路径中并返回,如果在右子树中找到了目标结点,则将当前结点加入到路径中并返回,如果既不在左子树中,也不在右子树中,则说明目标结点不存在于当前子树中,返回空列表。
阅读全文