求二叉树中某一个节点的所有祖先节点的算法的完整代码
时间: 2024-02-28 17:56:20 浏览: 43
以下是求二叉树中某一个节点的所有祖先节点的算法的完整代码,使用了递归的方式实现:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def find_ancestors(root, target):
if root is None:
return []
if root.val == target:
return [root.val]
left_ancestors = find_ancestors(root.left, target)
if left_ancestors:
return [root.val] + left_ancestors
right_ancestors = find_ancestors(root.right, target)
if right_ancestors:
return [root.val] + right_ancestors
return []
```
其中,TreeNode 是二叉树节点的定义,find_ancestors 函数接收二叉树的根节点和目标节点的值,返回目标节点的所有祖先节点的值(从根节点到目标节点的路径上的所有节点值)。如果目标节点不存在,返回空列表。
该算法使用了递归的方式,先判断当前节点是否为目标节点,如果是则返回该节点值。否则,递归地在左右子树中查找目标节点,如果找到了,则将当前节点值加入到结果列表中,最终返回结果列表。如果左右子树均未找到目标节点,则返回空列表。