[代码随想录]Day18-二叉树part07

题目：530. 二叉搜索树的最小绝对差

思路：

一个关键问题——BST的中序遍历是由小到大的顺序，也就是说记录遍历的前一个节点，每次比较当前节点-前一个节点的值即可(因为由小到大所以当前>前一个)

代码：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var pre *TreeNode
var res int
func getMinimumDifference(root *TreeNode) int {
    pre = nil
    res = math.MaxInt64
    step(root)
    return res
}
func step(root *TreeNode) {
    if root == nil { // 空返回
        return 
    }
    step(root.Left) // 前
    if pre != nil { // 如果不是空就比较
        res = min(res, root.Val - pre.Val)
    }
    pre = root // 记录节点
    step(root.Right) // 后
}
func min(a,b int)int {
    if a < b {
        return a
    }
    return b
}

参考：

代码随想录

题目：501. 二叉搜索树中的众数

思路：

同上，不过有可能有多个众数，因此要额外加一个判断：

1. 如果和现在的最大值相等就添加
2. 如果比现在最大值大就清空后添加

代码：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var res []int
var count, maxCount int
var pre *TreeNode
func findMode(root *TreeNode) []int {
    res = []int{}
    count, maxCount = 0, 0
    pre = nil
    step(root)
    return res
}

func step(root *TreeNode) {
    if root == nil { // 返回空
        return
    }
    step(root.Left) // 前
    if pre == nil { // 如果为空就开始计数
        count = 1
    }else if pre.Val == root.Val { // 相等就记录数+1
        count++
    }else {  // 不相等重新计数
        count = 1
    }
    pre = root // 记录前一个节点
    if count == maxCount { // 和当前众数个数相同的往里添加
        res = append(res, root.Val)
    }
    if count > maxCount { // 比当前大清空后添加
        maxCount = count
        res = append([]int{},root.Val)
    }
    step(root.Right)
}

参考：

代码随想录

题目：236. 二叉树的最近公共祖先

思路：

1. 当遇到p或者q直接返回p或者q
2. 当一个节点的左子树和右子树都有返回值(p和q)，返回该节点
3. 只有一个子树有返回值，返回有返回值的子树
4. 没有返回值，返回nil

代码：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
 func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    if root == p || root == q{ // 找到子树先
        return root
    }
    left := lowestCommonAncestor(root.Left, p, q) // 左子树
    right := lowestCommonAncestor(root.Right, p, q) // 右子树
    if left == nil && right != nil { // 左nil 右有返回右
        return right
    }
    if left != nil && right == nil { // 右nil 左有返回左
        return left
    }
    if left != nil && right != nil { // 都有返回当前子树
        return root
    }
    return nil // 没有返回空
}

参考：

代码随想录