173. Binary Search Tree Iterator

문제

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