[LeetCode OJ] Binary Search Tree Iterator - Medium Algorithm

<Problem Link>


<Comment>

이문제는 일단 제대로 이해하는것이 반이상을 먹고 들어간다.
Binary Search Tree... 이다
Binary Tree는 누구나 쉽게 머릿속에 떠올릴 수 있으나,

Binary Search Tree... 하면
뭐 그저 이진트리만을 일단 떠올리기 쉽다.
내가 이말을 하는이유는 이 BST라는 단어가 이 문제의 풀이에 매우 중요한 역할을 하기 때문이다.

BST에 Pre-order traversal 을 진행하면 작은 값부터 큰값으로
오름차순 증가하는 element값을 순자척으로 얻을 수 있다!!

일단 상수 시간복잡도 안에 Tree의 특정 값을 리턴해 주어야 하고,
메모리 역시 Tree의 깊이로 제한이 걸려있다.

지금 내 Solution은 절대 최적이 아니라는것을 알지만 일단 Accepted 도장을 박은 풀이는 풀이이기에...


<Solution> Python - Accepted

================================================
실행시간 : 167ms
시간복잡도 (next() 에 대한) : O(1)
공간복잡도 (hasNext() 에 대한) : O(h)   h: tree의 높이
================================================

# Definition for a  binary tree node
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None

class BSTIterator:
# @param root, a binary search tree's root node
def __init__(self, root):
self.preorder_str = ""
self.num_idx = 1
if root:  # 작은수부터 차례로 입력된 String 문자열 생성
self.preorderSearch(root)
self.preorder_str_len = len(self.preorder_str)

def preorderSearch(self, node):
if node.left:
self.preorderSearch(node.left)
self.preorder_str += ";%s"%node.val
if node.right:
self.preorderSearch(node.right)

# @return a boolean, whether we have a next smallest number
def hasNext(self):
ret = True
if self.num_idx >= self.preorder_str_len:
ret = False
return ret

# @return an integer, the next smallest number
def next(self):
num = self.preorder_str[self.num_idx]
self.num_idx += 1
while (self.num_idx < self.preorder_str_len):
c = self.preorder_str[self.num_idx]
if c == ";":
self.num_idx += 1
break
num += self.preorder_str[self.num_idx]
self.num_idx += 1
return int(num)




통계 위젯 (블랙)

7179
1239
270136

GoogleAdsenseResponsive

Cluster map