题目描述

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

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

输入：root = [1,2], p = 1, q = 2
输出：1

提示：

  • 树中节点数目在范围 [2, 105] 内。
  • -109 <= Node.val <= 109
  • 所有 Node.val 互不相同 。
  • p != q
  • 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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func lowestCommonAncestor(root, p, q *TreeNode) (ans *TreeNode) {
	var postOrder func(node *TreeNode) int
	postOrder = func(node *TreeNode) int {
		if node == nil {
			return 0
		}

		isLeft := postOrder(node.Left)
		if isLeft == 2 {
			return 2
		}

		isRight := postOrder(node.Right)
		if isRight == 2 {
			return 2
		}

		if node == p || node == q {
			if isLeft == 1 || isRight == 1 {
				ans = node
				return 2
			}
			return 1
		}

		if isLeft == 1 && isRight == 1 {
			ans = node
			return 2
		}

		return isLeft + isRight
	}
	postOrder(root)

	return
}

func main() {
	// Example usage:
	// root := &TreeNode{Val: 3, Left: &TreeNode{Val: 5}, Right: &TreeNode{Val: 1}}
	// p := root.Left // Node with value 5
	// q := root.Right // Node with value 1
	// lca := lowestCommonAncestor(root, p, q)
	// fmt.Println(lca.Val) // Should print the value of the lowest common ancestor

	// [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
	root := &TreeNode{
		Val: 3,
		Left: &TreeNode{
			Val:  5,
			Left: &TreeNode{Val: 6},
			Right: &TreeNode{
				Val:   2,
				Left:  &TreeNode{Val: 7},
				Right: &TreeNode{Val: 4},
			},
		},
		Right: &TreeNode{
			Val:   1,
			Left:  &TreeNode{Val: 0},
			Right: &TreeNode{Val: 8},
		},
	}
	p := root.Left             // Node with value 5
	q := root.Left.Right.Right // Node with value 4
	lca := lowestCommonAncestor(root, p, q)
	println(lca.Val) // Should print the value of the lowest common ancestor, which is 3
}

上面的实现比较复杂，主要是通过递归返回值来判断当前节点是否为 p 或 q 的最近公共祖先。用 1 表示节点及其子树中只包含 p 或 q，2 表示节点及其子树中包含 p 和 q，而 0 表示节点及其子树中不包含 p 或 q。

进一步优化实现逻辑，深度优先的后序遍历二叉树，判断当前节点是否为 p 或 q，如果是则返回当前节点，否则递归遍历左子树和右子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	if root == nil || root == p || root == q {
		return root
	} else if left, right := lowestCommonAncestor(root.Left, p, q), lowestCommonAncestor(root.Right, p, q); left != nil && right != nil {
		return root
	} else if left == nil {
		return right
	} else {
		return left
	}
}