【代码随想录】算法训练计划21、22

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
}