[Golang][Leetcode][BinaryTree]刷題系列-530-Minimum Absolute Difference in BST

2021-09-09 241 words 2 minutes

/leetcode530_binarytree/golang_leetcode.png

Contents

530. Minimum Absolute Difference in BST

Level : Easy

原題連結 : Click

題目 :

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
}

最後祝福努力認真的各位 “All your dream of are hidden in your daily life” 我們峰頂見!!!