代码随想录算法训练营第十八天| 530.二叉搜索树的最小绝对差 ● 501.二叉搜索树中的众数 ● 236. 二叉树的最近公共祖先

题目：

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

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

示例 1：

输入：root = [4,2,6,1,3]
输出：1

示例 2：

输入：root = [1,0,48,null,null,12,49]
输出：1

思路：

1.直接法，中序遍历将元素压入数组，此时得到从小到大排列的数组，再求数组中差值最小的值

2.双指针法，中序递归，pre指向当前节点的前一个节点，比较pre和cur的值，不断更新差值最小的值

算法：

//双指针法
/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/
func getMinimumDifference(root *TreeNode) int {minV := math.MaxInt //初始化为无穷大// minV := int(^uint(0)>>1) 另一种初始化方法var pre *TreeNode  //记录前一个节点var travelsal func(node *TreeNode)travelsal = func(node *TreeNode) {if node == nil {return}//左travelsal(node.Left)//中if pre != nil {minV = min(minV, node.Val-pre.Val)}pre = node//右travelsal(node.Right)}travelsal(root)return minV}

//法二，直接法
/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/
func getMinimumDifference(root *TreeNode) int {//中序遍历压入数组，再比较数组差值tmpArr := make([]int, 0)var traversal func(node *TreeNode)traversal = func(node *TreeNode) {if node == nil {return}traversal(node.Left)tmpArr = append(tmpArr,node.Val)traversal(node.Right)}traversal(root)//minv要初始化为最大值minv := math.MaxIntfor i := 1; i < len(tmpArr); i++ {minv = min(minv, tmpArr[i]-tmpArr[i-1])}return minv}

注意：

1.初始化int的最大值有两种方式，一种是int(^uint(0)>>1)

• ^uint(0) 产生 uint 类型的全 1（二进制表示为全 1 的值）。
• ^uint(0) >> 1 将所有位右移一位，相当于将最高位的 1 变成了 0，从而得到 uint 类型的最大值的一半。

2.另一种是直接调用math函数：math.MaxInt

题目：

501. 二叉搜索树中的众数

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

• 结点左子树中所含节点的值 小于等于 当前节点的值
• 结点右子树中所含节点的值 大于等于 当前节点的值
• 左子树和右子树都是二叉搜索树

示例 1：

输入：root = [1,null,2,2]
输出：[2]

示例 2：

输入：root = [0]
输出：[0]

提示：

• 树中节点的数目在范围 [1, 104] 内
• -105 <= Node.val <= 105

思路：

1. 直接法，中序遍历，使用map记录每个元素出现次数，找出map中的众数，再将出现次数=众数的元素全部返回

算法：

//方法一：直接法
/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/
func findMode(root *TreeNode) []int {//直接法，map存储元素的出现次数mm := make(map[int]int, 0)var traversal func(node *TreeNode)traversal = func(node *TreeNode) {if node == nil {return}//中序遍历将元素的出现次数计入maptraversal(node.Left) //左mm[node.Val]++ //中traversal(node.Right)  //右}traversal(root)//res数组存最终结果res := make([]int, 0)x := 0//求众数for _, v := range mm {fmt.Printf("x=%d,v=%d",x, v)x = max(x, v)}//将众数的值加入数组，返回数组for k, v := range mm {if v == x {res = append(res, k)}}return res
}

/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/
func findMode(root *TreeNode) []int {//双指针法var pre *TreeNodecount, maxcount := 0, 0res := make([]int, 0)var taversal func(node *TreeNode)taversal = func(node *TreeNode){if node == nil {return}taversal(node.Left)if pre == nil {count=1} else if node.Val == pre.Val{count++} else {count = 1}pre = node//注意频率相等收获元素if count == maxcount {res = append(res, node.Val)}if count > maxcount {//清空resres = []int{}res = append(res, node.Val)maxcount = count}taversal(node.Right)}taversal(root)return res}

注意：

题目：

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

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

输入：root = [1,2], p = 1, q = 2
输出：1

提示：

• 树中节点数目在范围 [2, 105] 内。
• -109 <= Node.val <= 109
• 所有 Node.val 互不相同 。
• p != q
• p 和 q 均存在于给定的二叉树中。

思路：

1、自底向上查找，这样就可以找到公共祖先，二叉树回溯的过程就是从低到上

2、后序遍历（左右中）就是天然的回溯过程，可以根据左右子树的返回值，来处理中节点的逻辑

算法：

/*** 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 {// p 和 q 分别在 root 的左右子树中，所以 root 是最低共同祖先return root}if left != nil {// p 和 q 都在 root 的左子树中，或者其中一个就是 leftreturn left}if right != nil {// p 和 q 都在 root 的右子树中，或者其中一个就是 rightreturn right}// p 和 q 都不在 root 的子树中return nil
}

注意：