[Binary Tree General][Medium] 173. Binary Search Tree Iterator

Q. 주어진 binary tree를 in order traverse 한다고 할 때 아래 class를 디자인 하라. 

 

 

이때 next()와 HasNext()에 대해 O(1) TC와 O(h)의 mem space사용을 하도록 하라. 

 

 

Solution. 

 위 제한이 없다면, 객체 초기화 시점에 모든 데이터를 in order traverse하고 collect하고자 하는 데이터를 list등의 컨테이너에 넣으면 될 것이다. 

 하지만 제한으로 인해 다른 구조가 필요하다는 것을 알 필요가 있다. 

 

 우선 in order traverse를 하면, 왼쪽 child 이후 해당 노드를 방문하고 우측 child를 순서대로 방문하게 된다. 

 따라서 전체 순회 시 stack이 필요하다.

 

 또한 높이만큼의 메모리만 사용하라고 했으므로, 전체를 다 넣는 대신, 특정 노드 기준으로 left, right child중 한번에 한쪽만 넣어야 하고 순회 특성상 left를 먼저 처리해야 함을 알 수 있다. 

 

 위 논리대로 코드를 작성 해 본다. 

 

 

class BSTIterator {

    stack<TreeNode*> mBuff;

    void VisitLeft(TreeNode* node)
    {
        if(node == nullptr) return;

        mBuff.push(node);
        VisitLeft(node->left);
    }

public:
    BSTIterator(TreeNode* root) 
    {
        VisitLeft(root);
    }
    
    int next() {
        
        if(mBuff.size() == 0)   return -1;

        TreeNode* cur = mBuff.top();
        mBuff.pop();
        int ret = cur->val;
        VisitLeft(cur->right);
        return ret;
    }
    
    bool hasNext() {
        return mBuff.size()>0;
    }
};

코드 자체는 간단하다. 

 

 

결과.