Leetcode - 173. Binary Search Tree Iterator

문제

next()가 호출될때 마다 트리의 inorder 순회한 값을 하나씩 리턴하라.

Input
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
Output
[null, 3, 7, true, 9, true, 15, true, 20, false]

Explanation
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
  initial 함수에서 vector에 inorder 순회하여 값을 미리 넣고 O(n), next가 불릴때마다 O(1)에 값을 리턴. hasNext() 도 O(1).
• 풀이 2
  stack 사용 -> stack을 사용해 inorder순회하는 신박한 방법!
  • (1). root부터 left 에 있는 모든 노드를 stack에 삽입
  • (2). 항상 stack의 top에 있는 노드가 next()의 리턴값이 됨
  • (3). (2)에서 top 노드 right에 노드가 있다면 right노드 기준으로 다시 (1) 을 수행(모든 left 스택에 삽입)
• 좋은 문제 인것 같다!

풀이 1

class BSTIterator {
public:
    vector<int> inorder;
    int idx = 0;
    
    BSTIterator(TreeNode* root) {
        travel(root);
    }
    
    void travel(TreeNode* root) {
        if (!root)
            return;
        travel(root->left);    
        inorder.push_back(root->val);
        travel(root->right);    
    }
    
    int next() {
        return inorder[idx++];    
    }
    
    bool hasNext() {
        return idx < inorder.size();
    }
};

풀이 2 - stack 사용

class BSTIterator {
public:
    stack<TreeNode *> s;
    BSTIterator(TreeNode* root) {
        insert_stack(root);
    }
    
    void insert_stack(TreeNode *root) {
        while (root) {
            s.push(root);
            root = root->left;
        }
    }
    
    int next() {
        TreeNode *node = s.top();
        s.pop();
        if (node->right)
            insert_stack(node->right);
        return node->val;
    }
    
    bool hasNext() {
        return !s.empty();    
    }
};