[LeetCode] 173. Binary Search Tree Iterator - 이진탐색트리(Binary Search Tree) + 깊이우선탐색(DFS) JAVA

https://leetcode.com/problems/binary-search-tree-iterator/description/

코드설명

이진탐색트리(Binary Search Tree) + 깊이우선탐색(DFS) 를 활용합니다.

 

이진탐색트리의 조건으로는,

1. 각 노드는 최대 두개의 자식노드만을 가질 수 있습니다.

2. 왼쪽 자식노드값은 부모노드값보다 작아야 합니다.

3. 오른쪽 자식 노드값은 부모노드값보다 커야합니다.

 

이러한 조건을 통해, 탐색 시 O(log n) 안에 탐색이 가능해집니다.

 

문제의 입력예시와 함께 살펴보면,

BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next();    // return 3
bSTIterator.next();    // return 7
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 9
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 15
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 20
bSTIterator.hasNext(); // return False

1. 먼저 BSTIetartor 생성자가 실행하여, 루트에서부터 맨 왼쪽 노드까지 Stakc에 넣습니다. 이떄 pushLeft를 통해 맨 하단까지 내려간다는 점을 확인합니다.

2. next함수 실행하여 stack에서 값을 POP하고, 오른쪽 노드를 pushLeft를 통해 stack에 넣어갑니다.

 

주 로직은 이 2가지입니다.

코드

/**
 * 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 {
    Stack<TreeNode> st = new Stack<>();
    public BSTIterator(TreeNode root) {
        st.push(root);
        pushLeft(root.left);
    }
    
    public int next() {
        TreeNode node = st.pop();
        pushLeft(node.right);
        return node.val;
    }
    
    public boolean hasNext() {
        return !st.isEmpty();
    }

    private void pushLeft(TreeNode node){
        if(node != null){
            st.push(node);
            pushLeft(node.left);
        }
    }
}

/**
 * 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();
 */