본문 바로가기
Algorithm

173. Binary Search Tree Iterator

by happyMoons 2023. 12. 30.

문제

왼쪽, 오른쪽 포인터를 가지고 있는 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() 비교하여 다음 원소 존재 유무를 리턴합니다.  

댓글