代码求二叉树中某一个节点的所有祖先节点的算法
时间: 2024-03-02 14:48:30 浏览: 24
可以使用递归的方式来实现求二叉树中某一个节点的所有祖先节点的算法。具体步骤如下:
1. 从根节点开始遍历二叉树,如果找到目标节点,则说明已经找到了所有的祖先节点,直接返回。
2. 如果当前节点不是目标节点,则递归遍历左子树和右子树,直到找到目标节点。
3. 如果在左子树或右子树中找到了目标节点,则当前节点就是目标节点的祖先节点之一,将当前节点加入到一个结果集合中。
4. 最后返回结果集合。
下面是该算法的代码实现:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def get_ancestors(root, target):
if not root:
return []
if root == target:
return [root.val]
left_ancestors = get_ancestors(root.left, target)
if left_ancestors:
left_ancestors.append(root.val)
return left_ancestors
right_ancestors = get_ancestors(root.right, target)
if right_ancestors:
right_ancestors.append(root.val)
return right_ancestors
return []
```
其中,root 表示二叉树的根节点,target 表示目标节点。算法的时间复杂度为 O(n),其中 n 表示二叉树的节点数。