[LeetCode] 783. Minimum Distance Between BST Nodes

- Problem

783. Minimum Distance Between BST Nodes

---

- 내 풀이 1 (BFS, Iteration)

class Solution:
    def bfs(self, root: Optional[TreeNode]) -> List:
        node_vals = []
        q = deque([root])

        while q:
            node = q.popleft()
            node_vals.append(node.val)

            if node.left:
                q.append(node.left)
            
            if node.right:
                q.append(node.right)

        return node_vals

    def minDiffInBST(self, root: Optional[TreeNode]) -> int:
        answer = float('inf')
        node_vals = self.bfs(root)
        N = len(node_vals)
        node_vals.sort()

        for i in range(N - 1):
            answer = min(answer, node_vals[i+1] - node_vals[i])

        return answer

- 결과

주어진 트리를 순회하며 모든 값을 구하고, 오름차순으로 정렬하여 차이가 가장 작은 노드의 값을 구한다.

만약 정렬을 사용하지 않는다면, 다음과 같이 완전 탐색을 이용하여 정답을 구해야 한다.

for i in range(N-1):
	for j in range(i+1, N):
    	answer = min(answer, abs(stk[i] - stk[j]))

---

- 내 풀이 2(DFS, Recursion)

class Solution:
    min_diff: int = float('inf')

    def minDiffInBST(self, root: Optional[TreeNode]) -> int:
        def dfs(node, lower: int = -1, upper: int = -1) -> None:
            if not node:
                return
            
            if lower > -1:
                self.min_diff = min(self.min_diff, node.val - lower)
            
            if upper > -1:
                self.min_diff = min(self.min_diff, upper - node.val)
            
            dfs(node.left, lower, node.val)
            dfs(node.right, node.val, upper)

        dfs(root)
        return self.min_diff

- 결과

현재 노드의 왼쪽에 있는 값들은 현재 노드보다 작은 값, 현재 노드의 오른쪽에 있는 값들은 현재 노드보다 큰 값이라는 BST의 특성을 이용한 풀이 방법이다.