求二叉树中某一个节点的所有祖先节点的算法,并验证
时间: 2024-02-29 08:52:34 浏览: 21
求二叉树中某一个节点的所有祖先节点的算法可以通过递归实现。具体步骤如下:
1. 如果当前节点为空或者为目标节点,则返回空。
2. 如果当前节点的左子树或者右子树中存在目标节点,则当前节点是目标节点的祖先节点,将其加入结果集合中。
3. 递归查找当前节点的左子树和右子树,将查找结果加入结果集合中。
下面是 Python 代码的实现:
``` python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def find_ancestors(root: TreeNode, target: TreeNode) -> List[TreeNode]:
if root is None:
return []
if root == target:
return []
left_ancestors = find_ancestors(root.left, target)
if left_ancestors:
return [root] + left_ancestors
right_ancestors = find_ancestors(root.right, target)
if right_ancestors:
return [root] + right_ancestors
return []
```
为了验证这段代码的正确性,我构造了一棵二叉树,并查找其中一个节点的祖先节点。下面是 Python 代码的实现:
``` python
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
target = root.left.right
ancestors = find_ancestors(root, target)
print([node.val for node in ancestors])
```
输出结果为 [2, 1],验证了这段代码的正确性。