530.二叉搜索树的最小绝对差
二叉搜索树前序遍历，节点值是有序排列的
遍历过程中求解最小值
func getMinimumDifference(root *TreeNode) int {
preVal, minNum := -1, math.MaxInt64
var help func(root *TreeNode, minNum *int)
help = func(root *TreeNode, minNum *int){
if root == nil {
return
}
help(root.Left, minNum)
if preVal != -1 && root.Val - preVal < *minNum {
*minNum = root.Val - preVal
}
preVal = root.Val
help(root.Right, minNum)
}
help(root, &minNum)
return minNum
}
501.二叉搜索树中的众数
类似上题：需要辅助变量，preNode记录前一个节点，用于比较数值；count记录当前节点值出现次数；maxCount记录遍历到当前节点时众数的出现次数。
preNode != nil && preNode.Val == root.Val count++
preNode == nil || preNode != nil && preNode.Val != root.Val count = 1
如果当前count == maxCount，结果中追加(有多个众数)；如果count > maxCount，清空结果并追加当前节点值
func findMode(root *TreeNode) []int {
res := []int{}
pre := &TreeNode{}
count, maxCount := 0, 0
var help func(root *TreeNode)
help = func(root *TreeNode) {
if root == nil {
return
}
help(root.Left)
if pre != nil && pre.Val == root.Val {
count++
}else{
count = 1
}
pre = root
if count == maxCount {
res = append(res, root.Val)
}
if count > maxCount {
maxCount = count
res = []int{}
res = append(res, root.Val)
}
help(root.Right)
}
help(root)
return res
}
236.二叉树的最近公共祖先
二叉树自底向上查找，后序遍历，可以根据左右子树的返回值，处理中间节点
若root是p、q的最近公共祖先包括三种情况：节点p、q分别在root的左、右子树；p = root, q 在其子树中；q = root, p在其子树中；
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 {
return right
}
if right == nil {
return left
}
return root
}
