530. Minimum Absolute Difference in BST

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

Solution1 for BST: 미디엄 스트리밍


사고방식: Time Complexity: O(N) Space Complexity: O(N) 귀속 캐시

Solution2 for BT: 스트리밍 + TreeSet


사고방식: Time complexity O(NlgN), Space complexity O(N)
Solution1-BST Code:
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;
    }
    
}

Solution2-BT Code:
public class Solution {
    TreeSet set = new TreeSet<>();
    int min = Integer.MAX_VALUE;
    
    public int getMinimumDifference(TreeNode root) {
        if (root == null) return min;
        
        if (!set.isEmpty()) {
            if (set.floor(root.val) != null) {
                min = Math.min(min, root.val - set.floor(root.val));
            }
            if (set.ceiling(root.val) != null) {
                min = Math.min(min, set.ceiling(root.val) - root.val);
            }
        }
        
        set.add(root.val);
        
        getMinimumDifference(root.left);
        getMinimumDifference(root.right);
        
        return min;
    }
}

좋은 웹페이지 즐겨찾기