Contents

# 530. Minimum Absolute Difference in BST

## 題目 :

Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.

### Example :

Note

Example 1:

Input: root = [4,2,6,1,3] Output: 1

Example 2:

Input: root = [1,0,48,null,null,12,49] Output: 1

#### 解題思路 :

• 這題的概念可以參考 leetcode98題解利用inorder特性的解法

• BST若用inorder遍歷就會形成一個由小到大的有序排列，利用這個特性這題會變得非常簡單

• 因為只是要找最小絕對差，那只要寫出Inorder遍歷的邏輯 + 一個一個比較數值並存下最小絕對差，就可以輕鬆解決這題瞜!!

### Recursive解法-Inorder

• time complexity: O(n) , space complexity: O(1)

Runtime: 8 ms, faster than 86.96% of Go online submissions for Minimum Absolute Difference in BST.

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 `````` ``````/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ import "math" func getMinimumDifference(root *TreeNode) int { pre := -1 var res = math.MaxInt64 var compareDiff func(*TreeNode) compareDiff = func(node *TreeNode) { if node.Left != nil { compareDiff(node.Left) } cur := node.Val if pre != -1 { diff := cur - pre if diff < res { res = diff } } pre = cur if node.Right != nil { compareDiff(node.Right) } } compareDiff(root) return res } ``````