剑指 Offer 68 - II. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

DFS

目标：找到子树同时包含 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
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

// DFS
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	minDepth := math.MaxInt
	var res *TreeNode
	var bp func(root *TreeNode) (pv, qv bool, d int)
	bp = func(root *TreeNode) (pv, qv bool, d int) {
		// 返回以root为头节点的树是否含有p和q和它的深度
		if root == nil {
			return false, false, 0
		}

		pv1, qv1, d1 := bp(root.Left)
		pv2, qv2, d2 := bp(root.Right)
		d = max(d1, d2) + 1
		if pv1 || pv2 || root.Val == p.Val {
			pv = true
		}
		if qv1 || qv2 || root.Val == q.Val {
			qv = true
		}
		if pv && qv && d < minDepth {
			res = root
			minDepth = d
		}
		return
	}
	bp(root)
	return res
}

更好的 DFS

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	if root.Val == p.Val || root.Val == q.Val {
		return root
	}
	left := lowestCommonAncestor(root.Left, p, q)
	right := lowestCommonAncestor(root.Right, p, q)
	if left != nil && right != nil {
        // root 左右子树即为p和
		return root
	}
	if left == nil {
		return right
	}
	return left
}