门户网站开发 南宁,uniapp商城源码,小程序直播,抖音代运营合作协议书范本题目#xff1a; 530. 二叉搜索树的最小绝对差 给你一个二叉搜索树的根节点 root #xff0c;返回 树中任意两不同节点值之间的最小差值 。 差值是一个正数#xff0c;其数值等于两值之差的绝对值。 示例 1#xff1a; 输入#xff1a;root [4,2,6,1,3]
输出#xff1a;…题目 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 {count1} 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 ! qp 和 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
} 注意
