Leetcode - 783. Minimum Distance Between BST Nodes
문제
Loading...
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
풀이
in-order traversal로 해결할 수 있다.
class Solution:
res = float("inf")
prev = -float("inf")
def minDiffInBST(self, root: TreeNode) -> int:
if root:
self.minDiffInBST(root.left)
self.res = min(self.res, root.val - self.prev)
self.prev = root.val
self.minDiffInBST(root.right)
return self.res
그런데 DFS 재귀는 항상 반복으로도 구현이 가능하다. Detail 페이지에서 가장 빠른 실행속도를 보인 답변을 조금 수정한 코드는 다음과 같다.
class Solution:
def minDiffInBST(self, root: TreeNode) -> int:
min_diff = float("inf")
stack = [(root, -float("inf"), float("inf"))]
while stack:
node, low, high = stack.pop()
if node:
min_diff = min(min_diff, node.val - low, high - node.val)
stack.append((node.right, node.val, high))
stack.append((node.left, low, node.val))
return min_diff
스택에 노드, 최소값, 최대값을 같이 넣는게 진짜 좋은 아이디어다.