2022-03-19：已知一棵二叉树上所有的值都不一样， 给定这棵二叉树的头节点head， 给定一个整型数组arr，arr里放着不同的值，每个值一定在树上 返回

2022-03-19：已知一棵二叉树上所有的值都不一样，

给定这棵二叉树的头节点head，

给定一个整型数组arr，arr里放着不同的值，每个值一定在树上

返回数组里所有值的最低公共祖先。

答案2022-03-19：

递归。

代码用golang编写。代码如下：

代码语言：go复制

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)
	}
}

执行结果如下：

在这里插入图片描述

二叉树 编程算法

0 人点赞