PattySung

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 1:

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

Example 2:

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

<解題>

由於是InOrder，所以已經sorted了，故從左邊開始至右邊
去計算兩兩相減的值並更新至min，且更新prev的值


public class Solution {
    int min = Integer.MAX_VALUE;
    Integer prev = null;

    public int getMinimumDifference(TreeNode root) {
        if (root == null) return min;
        
        getMinimumDifference(root.left);
        
        if (prev != null) {
            min = Math.min(min, root.val - prev);
        }
        prev = root.val;
        
        getMinimumDifference(root.right);
        
        return min;
    }
}

In-Order traverse Time complexity: O(N) Space complexity: O(1)

Leetcode-530. Minimum Absolute Difference in BST

<解題>