力扣二叉树–第三十七天

本文介绍: 废话不多说，能学到东西！功不唐捐！学习使人快乐！掌控感让人舒适！学无止境！

前言

废话不多说，能学到东西！功不唐捐！

内容

一、二叉 搜索树的最小 绝对差

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

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

中序 遍历

中序遍历将值保存在一个数组中再进行遍历求解

func getMinimumDifference(root *TreeNode) int {
   
   res:=dfs(root)
   var val []int
    for i:=0;i&lt;len(res)-1;i++{
      val=append(val,res[i+1]-res[i])
    }
  return findMin(val)
   
}
func findMin(nums []int)int{
    min:=nums[0]
  for _,v:=range nums{
      if v&lt;min{
          min=v
      }
  }
    return min
}
// func findMin(nums []int)int{
//     min:=nums[0]
//     for i:=0;i&lt;len(nums)-1;i++{
//        if nums[i+1]&lt;min{//第一遍写这个竟然写错了没发现 
//            min=nums[i+1]
//         }
//     }
//     return min
// }

func dfs(root *TreeNode)(res []int){
       if root==nil{
           return 
       }
      res=append(res,dfs(root.Left)...) 
      res=append(res,root.Val)
      res=append(res,dfs(root.Right)...)
   return
}

在中序遍历的过程中用 pre 变量保存前驱节点的值，这样即能边遍历边更新答案，不再需要显式创建数组来保存。

func getMinimumDifference(root *TreeNode)int{
   var prev *TreeNode// 保留前一个节点的指针
   min:=math.MaxInt64
   //var min math.MaxInt64   math.MaxInt64 是一个常量，表示 64 位有符号整数的最小值。你不能直接使用 var min math.MaxInt64 这样的代码来定义一个变量并将其赋值为 math.MaxInt64
   var dfs func(root *TreeNode)
    dfs=func (root *TreeNode){
      if root==nil{
          return 
      }
      dfs(root.Left)
      if prev!=nil&amp;&amp;root.Val-prev.Val<min{
          min=root.Val-prev.Val
      }
      prev=root
      dfs(root.Right)
  }
  dfs(root)
  return min
}