Zenn
🖋

LeetCode 530. Minimum Absolute Difference in BST

に公開
Go
LeetCode
tech

はじめに

LeetCode 「530. Minimum Absolute Difference in BST」の問題をGoで解きました。

問題

https://leetcode.com/problems/minimum-absolute-difference-in-bst/description

問題文

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.

和訳
バイナリサーチツリー（BST）のルートが与えられたとき、ツリー内の任意の2つの異なるノードの値の差の絶対値の最小値を返す。

例

         4          
      /     \        
     2       6    
    / \     
   1   3 

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

         1          
      /     \        
     0      48    
            / \     
           12  49 

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

制約

  • The number of nodes in the tree is in the range [2, 104].
  • 0 <= Node.val <= 105

解答

二分探索木 Binary Search Tree

二分探索木は二分木の一種で以下の特徴があります。

  • 左の子は親より小さい（左部分木にはそのノードより小さい値のみ含まれる）
  • 右の子は親より大きい（右部分木にはそのノードより大きい値のみ含まれる）
  • 中間順で木をたどると昇順の値列が得られる

中間順 In-order Traversal

二分木の走査の方法の一つで、ノードを次の順番で訪れます。
左部分木→現在のノード→右部分木

以下の二分木だと、1 → 2 → 3 → 4 → 6 の順となります。

         4          
      /     \        
     2       6    
    / \     
   1   3

BSTでは、中間順に並べた値は必ず昇順になるため、任意の２ノードの差よりも隣接ノードの間の差が最初になります。
今回の問題は、中間順でノードをたどりながら隣り合うノードを比較し、最小差を記録していくという方法で実装できます。

コード

func getMinimumDifference(root *TreeNode) int {
    var prev *int
    minDiff := math.MaxInt32

    var dfs func(node *TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil {
            return
        }
        
        dfs(node.Left)

        if prev != nil {
            diff := node.Val - *prev
            if diff < minDiff {
                minDiff = diff
            }
        }
        prev = &node.Val

        dfs(node.Right)
    }
    
    dfs(root)
    return minDiff
}

prev は最初nilで、前のノードがまだ存在しないことを示しています。
差分の計算は２つ以上のノードがないとできないため、このような初期化を行なっています。

計算量

  • 時間的計算量：O(n)
    • n はノード数（各ノードを1回ずつ訪れる）
  • 空間的計算量：O(h)
    • h は木の高さ（再帰呼び出しのスタックが木の高さ分使われる）

参考

二分木の問題は、以下の記事でも紹介していますので、参考にしてください。

GitHubで編集を提案

Discussion