代码随想录 day21 第六章二叉树part07

本文主要是介绍代码随想录 day21 第六章二叉树part07，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

今日内容

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

● 501.二叉搜索树中的众数

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

详细布置

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

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

思路
- 直白想法
  - 中序遍历可以得到一个有序节点值序列
    1. 先中序排列二叉树
    2. 暴力找最小差
- 双指针
  - 中序遍历二叉树+双指针
    - 左【pre】+中【cur】
    - 中【pre】+右【cur】

题解

递归

func getMinimumDifference(root *TreeNode) int {res := math.MaxIntvar pre *TreeNode = nilvar traversal func(cur *TreeNode)traversal = func(cur *TreeNode) {if cur == nil {return}//左traversal(cur.Left)//中if pre != nil {res = min(res, cur.Val-pre.Val)}pre = cur//中是相对于右而言的pre//右traversal(cur.Right)}traversal(root)return res}

迭代

func getMinimumDifference(root *TreeNode) int {stack := make([]*TreeNode, 0) //存储节点的栈var cur *TreeNode = root      //当前节点指针var pre *TreeNode = nil       //前一个节点的指针res := math.MaxIntfor cur != nil || len(stack) > 0 {if cur != nil { // 指针来访问节点，访问到最底层stack = append(stack, cur) // 将访问的节点放进栈cur = cur.Left             //左} else {cur = stack[len(stack)-1] //取出栈底元素,左左元素stack = stack[:len(stack)-1]if pre != nil {res = min(res, cur.Val-pre.Val)}pre = curcur = cur.Right}}return res
}

2. 二叉搜索树中的众数

关联 leetcode 501.二叉搜索树中的众数

和 530差不多双指针思路，不过这里涉及到一个很巧妙的代码技巧。

可以先自己做做看，然后看我的视频讲解。

https://programmercarl.com/0501.二叉搜索树中的众数.html

视频讲解：不仅双指针，还有代码技巧可以惊艳到你！ | LeetCode：501.二叉搜索树中的众数_哔哩哔哩_bilibili

题解

自己解法

使用一个map来存储元素出现次数

/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/
func findMode(root *TreeNode) []int {rets := make([]int, 0)countMap := make(map[int]int)var traversal func(root *TreeNode)traversal = func(root *TreeNode) {if root == nil {return}countMap[root.Val]++if root.Left != nil {traversal(root.Left)}if root.Right != nil {traversal(root.Right)}}traversal(root)maxCount := 0for k, v := range countMap {if v > maxCount {maxCount = vrets = make([]int, 0)rets = append(rets, k)} else if v == maxCount {rets = append(rets, k)}}return rets
}

二叉搜索树一定是中序遍历

遍历得到的二叉树节点一定是有序的
讲解双指针法
和自己的思路不差, 省去了map的使用, 提升效率

func findMode(root *TreeNode) []int {ret := make([]int, 0)var pre *TreeNode = nilcount := 0maxCount := 0var traversal func(cur *TreeNode)traversal = func(cur *TreeNode) {if cur == nil {return}traversal(cur.Left) //Left/* Middle */if pre == nil {count = 1 //初始化遍历, 首次走到叶子节点} else if pre.Val == cur.Val {count++ //找到重复元素, 当前元素出现次数递加} else {count = 1 //当前元素是新出现的元素, 重置出现次数}pre = cur //将前一个元素指针指向当前元素if count == maxCount {ret = append(ret, cur.Val)}if count > maxCount {maxCount = countret = []int{cur.Val}}traversal(cur.Right) //Right}traversal(root)return ret
}

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

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

思路
- 题目强调
  - 输入节点的值互不相同
  - p、q节点一定存在于所给二叉树中
    - 一定能找到祖先节点，最终结果一定不是nil
- 公共祖先
  - 祖先的左、右节点或者它自己分别包含一个指定节点即可
  - 从底向上回溯查找即可
    - 选用后序遍历
      - 先找左、右孩子，再处理父亲节点本身
        如果左右子树恰好包含要找的元素，这时的父亲节点就是一个祖先

题解

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {if root == nil {return nil}if root == q || root == p {return root}//左子树left := lowestCommonAncestor(root.Left, p, q)//右子树right := lowestCommonAncestor(root.Right, p, q)//中if left != nil || right != nil {//当前节点的左子树，右子树恰好包含元素，该节点就是最近公共祖先return root}//走到下面就是至少左右有一个是nilif right != nil {//说明目标节点是通过right返回的return right}if left != nil  {//说明目标节点是通过left返回的return left}  return nil}