已知有—棵以二叉链表存储的二叉树,root指向根结点,p指向二叉树中任一结点,如何求从根结点到p所指结点之间的路径?
时间: 2024-05-10 10:17:19 浏览: 44
可以使用递归的方式实现,具体步骤如下:
1. 如果根节点root为空,直接返回空路径。
2. 如果根节点root就是p所指节点,返回包含根节点的路径。
3. 如果p所指节点在左子树中,则递归求解左子树,得到从根节点到p所指节点的路径,并在路径末尾添加根节点。
4. 如果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 []
if root == p:
return [root]
left_path = find_path(root.left, p)
if left_path:
return [root] + left_path
right_path = find_path(root.right, p)
if right_path:
return [root] + right_path
return []
```
在使用时,调用 `find_path(root, p)` 即可得到从根节点到p所指节点的路径。
阅读全文