86.md

在二叉树中找到两个节点的最近公共祖先

题目

给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。

要求：空间复杂度 O(1)，时间复杂度 O(n)

注：本题保证二叉树中每个节点的val值均不相同

示例

输入：[3,5,1,6,2,0,8,#,#,7,4],5,1

返回值：3

所以节点值为5和节点值为1的节点的最近公共祖先节点的节点值为3，所以对应的输出为3

思路

• 【划重点】【普通二叉树】【不保证大小关系】【只可以判断 nil】
• 从上往下搜索，发现目标或者找到梢节了再往上返回
• 左右节点都没有就返回nil，即代表没有找到目标
• 左右只有一侧返回，说明找到了一个目标，那么返回
• 如果左右节点都有值，那这个节点即是最近公共祖先

实现

func lowestCommonAncestor(root *TreeNode, p int, q int) int {
	node := Core(root, p, q)
	return node.Val
}

// 递归判断 nil
func Core(root *TreeNode, p int, q int) *TreeNode {
	// 【稍节】没有找到
	if root == nil {
		return nil
	}
	// 找到了其中一个
	if p == root.Val || q == root.Val {
		return root
	}
	left := Core(root.Left, p, q)
	right := Core(root.Right, p, q)
	// 【左右】都没有找到
	if left == nil && right == nil {
		return nil
	}
	// 返回找到的一侧
	if left == nil {
		return right
	}
	if right == nil {
		return left
	}
	// 左右子树上均能找到,那这个节点即是最近公共祖先
	return root
}