[LeetCode] 530. Minimum Absolute Difference in BST

Minimum Absolute Difference in BST - LeetCode

 

이진 검색 트리(BST)의 루트가 주어졌을 때, 트리에 있는 서로 다른 두 노드의 값 사이의
최소 절대값 차이를 반환하는 문제입니다.

 

즉, 트리를 탐색해야합니다.

 

트리탐색 방법

PreOrder : self -> left -> right

PostOrder: left -> right -> self

InOrder: left -> self -> right

 

이진 검색 트리는 InOrder로 탐색을하면 정렬된 상태의 탐색이 가능합니다.

그 이유는 루트기준 왼쪽에 작은값, 오른쪽에 큰값을 갖는 형태이기 때문입니다.

문제접근

트리를 탐색하려면 재귀를 사용하는것이 제일 편합니다.

트리를 탐색하며 현재 노드와 이전 노드의 Min값을 구해서 반환해야겠다고 생각했습니다.

 

init은 처음 노드를 들어갔다고 알려주는 flag입니다.

첫 노드는 prev가 없기때문에 만든것입니다.

  public boolean init;
    int min;
    int prev;

    public int getMinimumDifference(TreeNode root) {
        init = false;
        min = Integer.MAX_VALUE;
        inorder(root);
        return min;
    }
    
    public void inorder (TreeNode root) {
        if (root == null) return;

        inorder(root.left);
        if (!init){
            init = true;
        } else {
            min = Math.min(min, root.val - prev);
        }
        prev = root.val;
        inorder(root.right);
    }

 

시간복잡도

트리를 탐색하는데 걸리는 시간은 O(log n)이지만 특정 요소를 탐색하는데 필요한 시간복잡도 입니다.

지금은 문제 요구사항에 따라 모든 트리를 탐색하고 있습니다.

 

O(n)의 시간복잡도를 갖고있습니다.

 

다른사람의 풀이

Stack을 사용해서 풀고있습니다.

 

저는 개인적으로 재귀형식의 트리탐색을 선호합니다.

그 이유는 Stack은 별도의 저장공간이 필요하고, 구현방법이 재귀형식보다 까다롭다고 생각됩니다.

 

하지만, 다양한 방법으로 문제를 접근하기위해 익혀두는것은 좋은것 같습니다.

 

      public int getMinimumDifference(TreeNode root) {
       if(root == null) return 0;
       Stack<TreeNode> stack = new Stack<>();
       int res = Integer.MAX_VALUE;
       TreeNode prev = null, curr = root;
       while(curr != null || ! stack.isEmpty()) {
           while(curr != null) {
               stack.push(curr);
               curr = curr.left;
           }
           curr = stack.pop();
           if(prev != null) {
                res = Math.min(res, Math.abs(curr.val - prev.val));
            }
            prev = curr;
            curr = curr.right;
       } 
       return res;
    }

 

느낀점

Tree를 탐색하는 방법은 기본적으로 잘 익혀두어야 겠습니다!

DFS로 탐색하는것은 Stack으로 탐색하는것으로 바꿔 연습해보면 좋을것 같습니다.

 

참고

https://www.youtube.com/watch?v=KLX44z_NnYc