代码随想录 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}
  

9. 题外话

1. 求最小公共祖先，需要从底向上遍历，那么二叉树，只能通过后序遍历（即：回溯）实现从底向上的遍历方式。
2. 在回溯的过程中，必然要遍历整棵二叉树，即使已经找到结果了，依然要把其他节点遍历完，因为要使用递归函数的返回值（也就是代码中的left和right）做逻辑判断。
3. 要理解如果返回值left为空，right不为空为什么要返回right，为什么可以用返回right传给上一层结果。

这篇关于代码随想录 day21 第六章 二叉树part07的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---