[Leetcode/C#] 530. Minimum Absolute Difference in BST

 

문제링크 

https://leetcode.com/problems/minimum-absolute-difference-in-bst/?envType=study-plan-v2&envId=top-interview-150

 

530. Minimum Absolute Difference in BST

 

 

기억하면 좋을 것 

내가 풀고싶은대로 풀었더니 Time Limit Exceeded  에러가 난다. O(n^2)

내가 푼 코드 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public int GetMinimumDifference(TreeNode root) {
        int min = int.MaxValue;
        void inorderTraverse(TreeNode root, int targetVal)
        {
            if(root == null) return ;
            
            if(root.val != targetVal) min = Math.Min(min, Math.Abs(targetVal - root.val));
            
            inorderTraverse(root.left, targetVal);
            inorderTraverse(root.right, targetVal);
            if(root.left != null) inorderTraverse(root.left, root.left.val);
            if(root.right != null) inorderTraverse(root.right, root.right.val);
        }

        inorderTraverse(root, root.val);
        return min;
    }
}

 

Run 을 했을때 정답이기는 했으나 Submit 을 했을때 Time Error Exceeded 가 난 이유는 내가 BST 에 대한 이해가 없었고 그 특성을 전혀 고려하지않았기 때문이다. 

 

Binary Search Tree (이진탐색트리) 즉 BST 의 특성은 아래와 같다. - 모든 노드에 대해, 왼쪽 서브트리의 모든 노드 값이 현재 노드의 값보다 작다. - 모든 노드에 대해, 오른쪽 서브트리의 모든 노드값이 현재 노드의 값보다 크다. 

 

이 특성 때문에 이진탐색트리를 중위순회 (inorder traverse) 하면 오름차순으로 노드를 순회할 수 있다. 아래의 예시를 보자 

    4
   / \
  2   6
 / \
1   3

 

위 BST 의 중위순회 순서는

1>2>3>4>6 이다.

 

BST 와 중위순회의 특성을 사용하면 한번의 순회만으로 노드간의 최소 값 차이를 구할 수 있는 것이다!

 

 

소감

BST 에서 중위순회 = 오름차순순회 임을 기억하자!

easy 이면서 내가 몰랐던 개념을 알 수 있어서 좋았다. 

 

해결 코드

 

public class Solution {
    int min = int.MaxValue;
    TreeNode prev = null;

    public int GetMinimumDifference(TreeNode root) {
        
        inorderTraverse(root);
        return min;
    }

    void inorderTraverse(TreeNode node)
    {
        if(node == null) return;

        inorderTraverse(node.left);//left node
        if(prev != null)
        {
            min = Math.Min(min, node.val - prev.val );
        }
        prev = node;//current node
        inorderTraverse(node.right);//right node
    }
}

 

 

 

Submission Detail