算法训练营day18, 二叉树7
import "math"
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func getMinimumDifference(root *TreeNode) int {
//初始一个最大值
result := math.MaxInt64
var prev *TreeNode
//同样也要内部封装一个递归函数
var treeTraversal func(tree *TreeNode)
treeTraversal = func(tree *TreeNode) {
if tree == nil {
return
}
treeTraversal(tree.Left)
//如果前一个节点不为空，且当前节点值与上一个节点值差小于result，则把这个差值赋给result
if prev != nil && tree.Val-prev.Val < result {
result = tree.Val - prev.Val
}
prev = tree
treeTraversal(tree.Right)
}
treeTraversal(root)
return result
}
func findMode(root *TreeNode) []int {
//设置返回数组为空
result := []int{}
//统计出现次数
count := 1
//最大次数
maxCount := 1
var prev *TreeNode
//同样还是要内部创建递归函数
var traversal func(tree *TreeNode)
traversal = func(tree *TreeNode) {
if tree == nil {
return
}
traversal(tree.Left)
//如果上一个节点值与当前节点值相等，count累计加1,不相等则重新从1计算
if prev != nil && tree.Val == prev.Val {
count++
} else {
count = 1
}
if count >= maxCount {
//如果统计次数大于最大统计，则把result数组清空并把当前值赋给数组result，否则result增加一个值
if count > maxCount {
result = []int{tree.Val}
} else {
result = append(result, tree.Val)
}
maxCount = count
}
prev = tree
traversal(tree.Right)
}
traversal(root)
return result
}
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
if root == nil || root == p || root == q {
return root
}
//后序遍历左右中
left := lowestCommonAncestor(root.Left, p, q)
right := lowestCommonAncestor(root.Right, p, q)
if left != nil && right != nil {
return root
} else if left == nil && right != nil {
return right
} else if left != nil && right == nil {
return left
} else {
return nil
}
}