문제
왼쪽, 오른쪽 포인터를 가지고 있는 TreeNode 클래스를 생성자 파라미터로 전달받아
next(), hasNext() 메소드 기능을 가지고 있는 BSTIterator 라는 클래스를 구현하는 문제입니다.
next() 메소드는 in-order 방식으로 순회했을때 다음 원소를 리턴하고,
hasNext() 메소드는 in-order 방식으로 순회했을때 다음 원소가 있으면 true, 없으면 false 를 리턴해야합니다.
문제 풀이 코드
class BSTIterator {
List<Integer> list;
int index = 0;
public BSTIterator(TreeNode root) {
list = new ArrayList<>();
inorderToList(root);
}
private void inorderToList(TreeNode root) {
if(root == null) return;
inorderToList(root.left);
list.add(root.val);
inorderToList(root.right);
}
public int next() {
return list.get(index++);
}
public boolean hasNext() {
return list.size() > index;
}
}
1. 생성자에 TreeNode 가 주어지면 in-order 방식으로 미리 순회해서 List 에 담습니다.
2. next() 메소드가 호출되면 index 변수를 활용하여 List 의 0번째 원소 부터 리턴합니다.
3. hasNext() 메소드가 호출되면 index 변수값과 list.size() 비교하여 다음 원소 존재 유무를 리턴합니다.
'Algorithm' 카테고리의 다른 글
2. Add Two Numbers (0) | 2024.01.01 |
---|---|
236. Lowest Common Ancestor of a Binary Tree (1) | 2023.12.31 |
129. Sum Root to Leaf Numbers (0) | 2023.12.29 |
114. Flatten Binary Tree to Linked List (0) | 2023.12.29 |
106. Construct Binary Tree from Inorder and Postorder Traversal (0) | 2023.12.27 |
댓글