最近公共祖先

树

说明

自底向上查找两个节点第一次汇合的位置；普通二叉树时间 O(n)。

分析

递归函数在子树中找到目标节点就返回该节点；如果左右子树各返回一个目标，当前节点就是最近公共祖先。若只在一侧找到结果，就继续向上返回它。

左侧返回目标1，右侧返回目标3，两侧都非空时返回当前根2。若当前根就是一个目标，它本身可以是另一个目标的祖先。实现比较节点身份而非数值，且假定两个目标都存在。

查看图表代码

适用前提与边界

这个简化实现假设两个目标都属于树，否则需要额外验证。 两个目标应为树中真实节点指针；缺失目标时本例可能返回另一个已找到的节点，不能据此证明公共祖先存在。

示例输入与调用

root := &Node{Value: 2, Left: &Node{Value: 1}, Right: &Node{Value: 3}}
	fmt.Println(LCA(root, root.Left, root.Right).Value)

运行输出

2

完整 Go 示例

package main

import "fmt"

type Node struct {
	Value       int
	Left, Right *Node
}

func LCA(root, a, b *Node) *Node {
	if root == nil || root == a || root == b {
		return root
	}
	l, r := LCA(root.Left, a, b), LCA(root.Right, a, b)
	if l != nil && r != nil {
		return root
	}
	if l != nil {
		return l
	}
	return r
}

func main() {
	root := &Node{Value: 2, Left: &Node{Value: 1}, Right: &Node{Value: 3}}
	fmt.Println(LCA(root, root.Left, root.Right).Value)
}