已知有—棵以二叉链表存储的二叉树,root指向根结点,p指向二叉树中任一结点,如何求从根结点到p所指结点之间的路径?
时间: 2024-05-14 09:16:21 浏览: 142
数据结构与算法 求二叉树上结点的路径
3星 · 编辑精心推荐
从根结点到p结点的路径可以看作是根结点到p结点的一条链,因此可以通过遍历二叉树来找到这条链。
可以采用递归的方式实现遍历,假设当前遍历到的结点为node:
1. 如果node为NULL,则返回空链。
2. 如果node为p结点,则返回只包含p的一条链。
3. 否则,分别在node的左子树和右子树中查找p结点,如果都找不到,则返回空链;如果只在左子树或右子树中找到了p结点,则返回包含node和p结点的一条链;如果在左右子树中都找到了p结点,则返回包含node、左子树中p结点和右子树中p结点的一条链。
下面是一个示例代码实现:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def find_path(root, p):
# 如果当前结点为空,则返回空链
if not root:
return []
# 如果当前结点为p结点,则返回只包含p的一条链
if root == p:
return [root]
# 在左子树中查找p结点
left_path = find_path(root.left, p)
# 如果在左子树中找到了p结点,则返回包含node和p结点的一条链
if left_path:
return [root] + left_path
# 在右子树中查找p结点
right_path = find_path(root.right, p)
# 如果在右子树中找到了p结点,则返回包含node和p结点的一条链
if right_path:
return [root] + right_path
# 如果左右子树中都没有找到p结点,则返回空链
return []
```
这样就可以通过调用`find_path(root, p)`函数来找到从根结点到p结点的路径了。
阅读全文