[파이썬 알고리즘] 14장 - BST 노드 간 최소 거리 (leetcode 783) - traversal 👍

leetcode.com/problems/minimum-distance-between-bst-nodes/

Minimum Distance Between BST Nodes - LeetCode

 

<문제>

Given a Binary Search Tree (BST) with the root node root,

return the minimum difference between the values of any two different nodes in the tree.

 

<예시>

Input: root = [4,2,6,1,3,null,null]
Output: 1
Explanation:
Note that root is a TreeNode object, not an array.

The given tree [4,2,6,1,3,null,null] is represented by the following diagram:

          4
        /   \
      2      6
     / \    
    1   3  

while the minimum difference in this tree is 1, it occurs between node 1 and node 2, also between node 3 and node 2.

 

---

자료구조 시간에 traversal에 대해 배웠지만 이런식으로 이용될 수 있다니! 정말 놀랐던 문제이다.

앞으로 tree 관련 문제를 풀 때 traversal는 항상 기억해두고 있어야 할 것 같다.

 

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def __init__(self):
        self.prev = -sys.maxsize
        self.result = sys.maxsize
        
    def minDiffInBST(self, root: TreeNode) -> int:
        print(root.val)
        if root.left:
            self.minDiffInBST(root.left)
        
        self.result = min(self.result, root.val-self.prev)
        self.prev = root.val
        
        if root.right:
            self.minDiffInBST(root.right)
        return self.result

우선 코드는 다음과 같다.

 

여기서 정말 놀랐던 아이디어는 최소 거리를 찾는데 in-order traversal를 이용한다는 것이다.

이 이야기는 아래에서 하도록 한다.

 

이 문제를 풀기 위해서는 BST에서 최소 거리를 찾기 위해선는 어떻게 해야할까?를 먼저 생각해보아야 한다.

나는 생각해내지 못하고, 책을 보고 깨달았다 : (

 

현재 노드와 최단 거리가 될 수 있는 노드는 어디에 위치할까?

• 1. 왼쪽 subtree에서 가장 오른쪽에 위치한 노드
• 2. 오른쪽 subtree에서 가장 왼쪽에 위치한 노드

이 2개의 노드가 후보이다. 둘 중 어느 노드가 최단 거리인지는 직접 봐야 알 수 있다.

 

 

그렇다면 왜 두 노드만 최단 거리의 후보가 되는 것인가?

• 1. 왼쪽 subtree에서 가장 오른쪽에 위치한 노드 (B)
  • = 현재 노드(A)보다 작은 값 중 가장 큰 값! 
  • 먼저 왼쪽 subtree에는 현재 노드보다 작은 값들만 위치한다는 것을 알아야 한다. (BST의 정의)
  • 또한 현재 노드(A)의 오른쪽 subtree에는 현재 노드보다 큰 값들만 위치한다는 것을 알아야 한다. (역시 BST의 정의)
  • 따라서 현재 노드(A)의 왼쪽 subtree에서 계속 오른쪽으로 간다면, 현재 노드보다 작은 값 중 가장 큰 값이 된다.
  • 이 노드 외 왼쪽 subtree에 위치하는 노드는 최단 거리의 후보조차 될 수 없다. (당연히 A와 B사이의 거리보다 클테니)
• 2. 오른쪽 subtree에서 가장 왼쪽에 위치한 노드 (C)
  • = 현재 노드보다 큰 값 중 가장 작은 값!
  • 먼저 오른쪽 subtree에는 현재 노드보다 큰 값들만 위치한다는 것을 알아야 한다. (BST의 정의)
  • 또한 현재 노드(A)의 왼쪽 subtree에는 현재 노드보다 작은 값들만 위치한다는 것을 알아야 한다. (역시 BST의 정의)
  • 따라서 현재 노드(A)의 오른쪽 subtree에서 계속 왼쪽으로 간다면, 현재 노드보다 큰 값 중 가장 작은 값이 된다.
  • 이 노드 외 오른쪽 subtree에 위치하는 노드는 최단 거리의 후보조차 될 수 없다. (당연히 A와 C사이의 거리보다 클테니)

 

 

여기서 어떻게 in-order가 사용되는가?

• 여기서 빨간색 숫자는 in-order traversal를 진행할 때 방문하는 순서이다.
• 파란색 숫자는 두 노드간의 거리를 비교하는 순서이다.
• 즉 파란색 1에서는 (2)-(1)와 기존 min_distance 비교하고, 더 작은 값을 min_distance로 하고,
• 다음 파란색 2에서는 (3)-(2)와 기존 min_distance 비교하고, 더 작은 값을 min_distance로 하고, ...
• 이 과정을 반복하면 최단거리가 구해지는 것이다!

 

처음 알고리즘 문제를 푸는 나에게는 정말 신기했던 문제 .. !

 

 

+) traversal 추가 정리

 

[파이썬 알고리즘] 14장 - BST 합 (traversal 개념)