在树中找到指定两个节点的最近根节点
时间: 2024-05-10 14:19:58 浏览: 10
可以使用树的深度优先搜索(DFS)算法,在遍历树的过程中记录每个节点的父节点,再从两个指定的节点开始往上找,直到找到最近的公共祖先节点即为最近根节点。具体实现可以参考以下代码:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def lowest_common_ancestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
"""
寻找指定两个节点的最近公共祖先节点
"""
# 记录每个节点的父节点
parent = {root: None}
# DFS遍历树,记录每个节点的父节点
def dfs(node: TreeNode):
if node.left:
parent[node.left] = node
dfs(node.left)
if node.right:
parent[node.right] = node
dfs(node.right)
dfs(root)
# 从p节点往上找,记录下所有的父节点
ancestors = set()
while p:
ancestors.add(p)
p = parent[p]
# 从q节点往上找,找到第一个在ancestors中出现的节点
while q not in ancestors:
q = parent[q]
return q
```
注意:以上代码只适用于树中每个节点的值唯一的情况。如果树中存在节点值相同的情况,需要针对性地修改代码才能正确计算最近公共祖先节点。