6-6 求根结点到x结点的路径(递归法)
时间: 2023-09-17 19:01:32 浏览: 277
求根节点到 x 结点的路径可以通过递归法来实现。递归函数的思路是,如果当前根结点是 x 结点,那么路径就是根结点本身。否则,递归搜索当前根结点的左子树和右子树,如果找到 x 结点,则将根结点加入路径,并返回该路径。
具体实现如下:
1. 如果根结点为 x 结点,返回只包含根结点的列表。
2. 在左子树中递归搜索 x 结点,找到路径后,将根结点加入路径,并返回该路径。
3. 在右子树中递归搜索 x 结点,找到路径后,将根结点加入路径,并返回该路径。
4. 如果左子树和右子树都没有找到 x 结点,则返回空列表。
以下是使用递归法求根结点到 x 结点的路径的示例代码:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def findPath(root, x):
if root.val == x:
return [root.val]
elif root.left:
left_path = findPath(root.left, x)
if left_path:
return [root.val] + left_path
elif root.right:
right_path = findPath(root.right, x)
if right_path:
return [root.val] + right_path
return []
```
上述代码定义了一个树节点类 `TreeNode`,以及一个名为 `findPath` 的递归函数。使用该函数可以求得根结点到 x 结点的路径。为了测试函数的正确性,我们可以创建一个二叉树,并调用 `findPath` 函数获取根结点到 x 结点的路径。
希望以上内容能对您有所帮助!