LeetCode - 173. Binary Search Tree Iterator java 풀이

푸는 방법을 생각해 내는게 어려운 문제.

방법을 알면 푸는건 간단한데 생각하기가 참 어렵다.

 

중요한건 노드 기준으로 볼 때

 

현재 노드의 왼쪽 아래 : 이것보다 작음

왼쪽의 왼쪽 아래 : 더 작음

현재 노드의 오른쪽 아래 : 이것보다 큼

현재 노드의 오른쪽 아래 : 내 위보다는 작음

 

이거를 기억하면 된다.

 

스택에 노드에서 왼쪽으로 가면서 쭉 넣어주고

next 할 때에는 노드에서 값을 꺼내서 보여주고, 현재 기준 오른쪽 노드를 기준으로도 쭉 확인해보기

hasNext 는 스택이 비어있지 않으면 가능

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class BSTIterator {
    // 사실 걍 스택
    Deque<TreeNode> nodes;
  
    public BSTIterator(TreeNode root) {
        // 풀이 방법
        // 현재 노드 기준 왼쪽 -> 작음, 오른쪽 -> 큼
            // 근데 현재 노드 기준 오른쪽에 있는것은 내 위에 있는것보다 작다.
               // 그러면 현재 노드를 응답하면서 오른쪽으로 또 검색해가면 될 것 같다.
                  // 시점은? 처음에 만들 때 넣어주고 응답할 때마다 검색을 반복하면 된다.
      
        nodes = new ArrayDeque<>();
        addLeft(root);
    }

    // 지금꺼 기준으로 왼쪽으로 내려가면 그게 무조건 최저값이 된다.
    // 현재 노드를 넣으면서 계속 왼쪽으로 내려가면 작은것부터 쌓이게 된다.
    private void addLeft(TreeNode node) {
        nodes.add(node);
        if(node.left != null) {
            // 왼쪽 계속 가면서
            while(node.left != null) {
                // 왼쪽꺼를 기준으로 계속 넣어준다.
                TreeNode left = node.left;
                node = left;
                nodes.add(node);
            }
        }
    }
    
    public int next() {
        // 뺄 때에는 일단 지금꺼를 보여주면 된다.
        // 그런데 Stack 에 현재 기준 오른쪽에 뭐가 있으면 그것도 넣으면 된다.
        // 왜냐면 현재 노드 기준으로 오른쪽 아래에 있는 것은 이것보다는 큰데 그 위보다는 작은 것이기 때문이다.
        // 근데 그 오른쪽 애도 결국 왼쪽으로 쭈루륵 이어질 수 있으니 그것도 위의 left 형태로 추가해주면 된다.

        TreeNode now = nodes.pollLast();
        if(now.right != null) {
            addLeft(now.right);
        }
        return now.val;
    }
    
    public boolean hasNext() {
        return !nodes.isEmpty();
    }
}

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator obj = new BSTIterator(root);
 * int param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 */