0530. Minimum Absolute Difference in B S T

# 530. Minimum Absolute Difference in BST#

## 题目 #

Given a binary search tree with non-negative values, find the minimum  absolute difference between values of any two nodes.

Example:

``````Input:

1
\
3
/
2

Output:
1

Explanation:
The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).
``````

Note:

## 解题思路 #

• 由于是 BST 树，利用它有序的性质，中根遍历的结果是有序的。中根遍历过程中动态维护前后两个节点的差值，即可找到最小差值。
• 此题与第 783 题完全相同。

## 代码 #

``````package leetcode

import (
"math"

"github.com/halfrost/leetcode-go/structures"
)

// TreeNode define
type TreeNode = structures.TreeNode

/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/

func getMinimumDifference(root *TreeNode) int {
res, nodes := math.MaxInt16, -1
dfsBST(root, &res, &nodes)
return res
}

func dfsBST(root *TreeNode, res, pre *int) {
if root == nil {
return
}
dfsBST(root.Left, res, pre)
if *pre != -1 {
*res = min(*res, abs(root.Val-*pre))
}
*pre = root.Val
dfsBST(root.Right, res, pre)
}

func min(a, b int) int {
if a > b {
return b
}
return a
}

func abs(a int) int {
if a > 0 {
return a
}
return -a
}
``````

Apr 8, 2023