二叉树指定结点到根节点的路径
时间: 2023-11-29 13:04:13 浏览: 65
二叉树指定结点到根节点的路径可以通过递归遍历二叉树得到。具体步骤如下:
1. 如果二叉树为空,直接返回空路径。
2. 如果二叉树根节点就是指定结点,则直接返回根节点。
3. 递归遍历左子树,如果找到指定结点,则将当前结点加入路径中,并返回路径。
4. 递归遍历右子树,如果找到指定结点,则将当前结点加入路径中,并返回路径。
5. 如果左右子树均未找到指定结点,则返回空路径。
下面是一个示例代码,用于实现二叉树指定结点到根节点的路径:
```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, node):
if not root:
return []
if root == node:
return [root.val]
left_path = find_path(root.left, node)
if left_path:
return [root.val] + left_path
right_path = find_path(root.right, node)
if right_path:
return [root.val] + right_path
return []
```
这个函数接受一个二叉树的根节点和一个指定结点,返回从指定结点到根节点的路径。如果指定结点不在二叉树中,返回空路径。