[ Top Interview 150 ] 530. Minimum Absolute Difference in BST

문제

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.

• Input : Binary Search Tree의 root node

  • 왼쪽 하위 노드들은 root 노드보다 값이 작고, 오른쪽 하위 노드들은 root 노드보다 값이 크다.

• Output : Tree 에 있는 node들 중 어떤 두 노드의 값 차이의 최소값

• 주어진 코드

  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
  
      TreeNode() {}
      TreeNode(int val) {this.val = val;}
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

알고리즘 전략

• 기본 전략. 모든 노드의 양 옆의 값 비교

  • 기본적으로 Binary Search Tree는 값들이 정렬되어 있다
  • 따라서 모든 노드의 양 옆의 값을 비교한다면, 그 값들 중 하나가 최소값이다.

• 양 옆의 값 비교 방법

  • Binary Search Tree의 특징 : 왼쪽 하위 노드들은 root 노드보다 값이 작고, 오른쪽 하위 노드들은 root 노드보다 값이 크다.
  • 그렇다면, 왼쪽 하위 노드 중 가장 큰 값이, root 노드의 이전 값이고, 오른쪽 하위 노드 중 가장 작은 값이 root 노드의 다음 값이다.

• 특정 노드 기준 최대/최소 값 찾는 방법

  • Binary Search Tree의 특징 : 왼쪽 하위 노드들은 root 노드보다 값이 작고, 오른쪽 하위 노드들은 root 노드보다 값이 크다.
  • 즉, root 노드부터 따라 내려와 어떤 노드의 오른쪽 노드가 없다면, 해당 노드가 해당 트리의 최대가 된다. 반대로 root 노드부터 따라 내려와 어떤 노드가 왼쪽 노드가 없다면 해당 노드가 해당 트리의 최소가 된다.

문제 답안

• Time complexity : $O(nlogn)$

class Solution {

    private static final int MAX_VALUE = 100_000;

    public int getMinimumDifference(TreeNode root) {
        int answer = MAX_VALUE;
        if (root.left != null) {
            answer = Math.min(root.val - getMaximum(root.left), answer);
            answer = Math.min(getMinimumDifference(root.left), answer);
        }
        if (root.right != null) {
            answer = Math.min(getMinimum(root.right) - root.val, answer);
            answer = Math.min(getMinimumDifference(root.right), answer);
        }
        return answer;
    }
    
    // 특정 트리의 최소값 구하기
    private int getMinimum(TreeNode root) {
        if (root.left == null) {
            return root.val;
        }
        return getMinimum(root.left);
    }

	// 특정 트리의 최대값 구하기
    private int getMaximum(TreeNode root) {
        if (root.right == null) {
            return root.val;
        }
        return getMaximum(root.right);
    }
}