已知一棵二叉树上所有的值都不一样，
给定这棵二叉树的头节点head，
给定一个整型数组arr，arr里放着不同的值，每个值一定在树上
返回数组里所有值的最低公共祖先。
递归。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
root := &TreeNode{val: 1}
root.left = &TreeNode{val: 2}
root.right = &TreeNode{val: 3}
root.left.left = &TreeNode{val: 4}
root.left.right = &TreeNode{val: 5}
root.right.left = &TreeNode{val: 6}
root.right.right = &TreeNode{val: 7}
ret := lowestCommonAncestor(root, []*TreeNode{root.left.left, root.right.right, root.right.left})
fmt.Println(ret.val)
}
type TreeNode struct {
val int
left *TreeNode
right *TreeNode
}
func lowestCommonAncestor(root *TreeNode, nodes []*TreeNode) *TreeNode {
set := make(map[int]struct{})
for _, node := range nodes {
set[node.val] = struct{}{}
}
return process(root, set, len(set)).find
}
type Info struct {
// 找没找到最低公共祖先
// 没找到，find = null
// 找到了最低公共祖先，find是最低公共祖先
find *TreeNode
// 我这颗子树上，删掉了几个节点！
removes int
}
func NewInfo(f *TreeNode, r int) *Info {
ans := &Info{}
ans.find = f
ans.removes = r
return ans
}
func process(x *TreeNode, set map[int]struct{}, all int) *Info {
if x == nil {
return NewInfo(nil, 0)
}
left := process(x.left, set, all)
if left.find != nil {
return left
}
right := process(x.right, set, all)
if right.find != nil {
return right
}
cur := 0
if _, ok := set[x.val]; ok {
cur = 1
}
delete(set, x.val)
if left.removes+right.removes+cur == all {
return NewInfo(x, all)
} else {
return NewInfo(nil, left.removes+right.removes+cur)
}
}执行结果如下：
