LeetCode 236. 二叉树的最近公共祖先
题目描述
思路分析
- 使用队列：我们可以使用队列进行层序遍历，同时记录每个节点的父节点。
- 记录父节点：在遍历过程中，使用一个哈希表来记录每个节点的父节点。
- 查找路径：从 p 和 q 开始，分别向上查找其所有祖先，并记录在集合中。
- 找到最近公共祖先：遍历 p 的祖先集合，找到第一个出现在 q 的祖先集合中的节点，即为最近公共祖先。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
// 使用队列来进行层序遍历
queue := []*TreeNode{root}
parent := make(map[*TreeNode]*TreeNode)
// 记录每个节点的父节点
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
if node.Left != nil {
parent[node.Left] = node
queue = append(queue, node.Left)
}
if node.Right != nil {
parent[node.Right] = node
queue = append(queue, node.Right)
}
}
// 查找 p 的所有祖先
ancestors := map[*TreeNode]bool{}
for p != nil {
ancestors[p] = true
p = parent[p]
}
// 查找 q 的祖先，找到第一个出现在 p 的祖先集合中的节点
for q != nil {
if ancestors[q] {
return q
}
q = parent[q]
}
return nil
}
- 时间复杂度：O(n)，其中
n是二叉树的节点数。- 空间复杂度：O(h)，其中
h是二叉树的高度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
if root == nil || root == p || root == q {
return root
}
// 递归查找左右子树
left := lowestCommonAncestor(root.Left, p, q)
right := lowestCommonAncestor(root.Right, p, q)
// 如果左右都不为空，说明当前节点是最近公共祖先
if left != nil && right != nil {
return root
}
// 否则返回非空的那一边
if left != nil {
return left
}
return right
}
- 时间复杂度：O(n)，其中
n是二叉树的节点数。- 空间复杂度：O(h)，其中
h是二叉树的高度。
1
write your code here
相似题目
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！