当前位置：首页 > article >正文

力扣二叉树--第三十七天

article 2024/9/22 17:41:26

前言

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

内容

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

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

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

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

中序遍历

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

func getMinimumDifference(root *TreeNode) int {
   
   res:=dfs(root)
   var val []int
    for i:=0;i<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<min{
          min=v
      }
  }
    return min
}
// func findMin(nums []int)int{
//     min:=nums[0]
//     for i:=0;i<len(nums)-1;i++{
//        if nums[i+1]<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&&root.Val-prev.Val<min{
          min=root.Val-prev.Val
      }
      prev=root
      dfs(root.Right)
  }
  dfs(root)
  return min
}