建站优化是什么,图文广告培训班多少钱,少儿编程加盟店8,网站的制作成品day 21
1、530. 二叉搜索树的最小绝对差
题目#xff1a; 给你一个二叉搜索树的根节点 root #xff0c;返回 树中任意两不同节点值之间的最小差值 。 差值是一个正数#xff0c;其数值等于两值之差的绝对值。
思路#xff1a;
利用了二叉搜索树的中序遍历特性用了双指…day 21
1、530. 二叉搜索树的最小绝对差
题目 给你一个二叉搜索树的根节点 root 返回 树中任意两不同节点值之间的最小差值 。 差值是一个正数其数值等于两值之差的绝对值。
思路
利用了二叉搜索树的中序遍历特性用了双指针不用也可以
func getMinimumDifference(root *TreeNode) int {// 好简单但是还是看了两眼题解因为恐惧下次要尝试脱离看题解了代码一刷中序遍历var pre *TreeNodemin : math.MaxInt64var travel func(node *TreeNode) travel func(node *TreeNode) {if node nil {return}travel(node.Left)if pre ! nil node.Val - pre.Val min {min node.Val - pre.Val}pre nodetravel(node.Right)}travel(root)return min
}2、501. 二叉搜索树中的众数
题目 给你一个含重复值的二叉搜索树BST的根节点 root 找出并返回 BST 中的所有 众数即出现频率最高的元素。 如果树中有不止一个众数可以按 任意顺序 返回。
思路
我第一次是自己写的用的笨方法遍历了两边map可以看看计数法也很简单但是不需要额外空间了卡哥的文档有写
func findMode(root *TreeNode) []int {// 放进mapmap1 : make(map[int]int, 0)zs : []int{}var travel func(node *TreeNode) travel func(node *TreeNode) {if node nil {return}travel(node.Left)map1[node.Val]travel(node.Right)} travel(root)a : 0for _,v : range map1 {if v a {a v}}for k,v : range map1 {if v a {zs append(zs, k)}}return zs
}3、236. 二叉树的最近公共祖先
题目 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”
思路
代码一刷后序遍历后序遍历很像回溯注意节点
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {// 代码一刷后序遍历if root nil {return root}if 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}if left ! nil {return left}if right ! nil {return right}return nil
}
day 22
1、235. 二叉搜索树的最近公共祖先
题目 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为“对于有根树 T 的两个结点 p、q最近公共祖先表示为一个结点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。” 例如给定如下二叉搜索树: root [6,2,8,0,4,7,9,null,null,3,5]
思路
利用二叉搜索树特点注意最后是 0
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {//代码一刷if root nil {return nil}for {if root.Val q.Val root.Val p.Val {root root.Left}if root.Val q.Val root.Val p.Val {root root.Right}if (root.Val - p.Val) * (root.Val - q.Val) 0 {return root}}return root
}2、701. 二叉搜索树中的插入操作
题目 给定二叉搜索树BST的根节点 root 和要插入树中的值 value 将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 新值和原始二叉搜索树中的任意节点值都不同。 注意可能存在多种有效的插入方式只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
思路
怎么我的写法就比卡尔的长了这么多代码
func insertIntoBST(root *TreeNode, val int) *TreeNode {if root nil {return TreeNode{Val:val}}travel(root,val)return root
}
func travel(node *TreeNode, val int) {if node nil {return}if node.Val val {if node.Left ! nil {travel(node.Left, val)} else {node.Left TreeNode{Val:val}return}}if node.Val val {if node.Right ! nil {travel(node.Right, val)} else {node.Right TreeNode{Val:val}return}}return
}3、450. 删除二叉搜索树中的节点
题目 给定一个二叉搜索树的根节点 root 和一个值 key删除二叉搜索树中的 key 对应的节点并保证二叉搜索树的性质不变。返回二叉搜索树有可能被更新的根节点的引用。 一般来说删除节点可分为两个步骤 首先找到需要删除的节点 如果找到了删除它。
思路
同样的利用二叉树特性
func deleteNode(root *TreeNode, key int) *TreeNode {// 看卡哥视频写的代码可以看不懂文档的代码if root nil {return nil}if key root.Val {if root.Left nil root.Right nil {return nil}if root.Left ! nil root.Right nil {return root.Left}if root.Right ! nil root.Left nil {return root.Right}// 左右都不为空cur : root.Rightfor cur.Left ! nil {cur cur.Left}cur.Left root.Leftreturn root.Right}if key root.Val {root.Right deleteNode(root.Right,key)}if key root.Val {root.Left deleteNode(root.Left,key)}return root
}
