leetcode 94 - iterative way dfs (inorder search)

Question

I got ' memroy limit exceeded ' error. And I dont find the reason why I got this..

below is my code

class Solution {
public:
vector inorderTraversal(TreeNode* root) {
// 중위순회를 반복적인 기법으로 어떻게 할 수 있을까?
// 우선 DFS : stack
// BFS : queue
// 이것부터 외워두자

    vector<TreeNode*> stack; // DFS
    vector<int> ans;   // 정답을 담을 배열

    if(root){
    stack.push_back(root);  // 재귀적x  
    }

    while(!stack.empty()){                // 여기서부터는 약간 스택 안에있는 하나의 노드를 기준으로 생각
                                          // 사실 재귀함수 자체가 메모리에 스택을 쌓는거이니깐
        TreeNode* current = stack.back();

        if(current->left){
            stack.push_back(current->left);
            continue;                 
        }

        ans.push_back(current->val);         // 중위순회가 이루어지는 부분 
        stack.pop_back();                    // 자기 자신도 여기서 없어져야할것이다 -> 그래야 다시 반복이 안되니깐

        if(current->right){
            stack.push_back(current->right);
        }
    }

    return ans;
}
};

I've tried not using 'continue' But still problem happens

1. Not recommend using 'continue'?
2. why memory exeeded ocurrs?

Answer 1

The problem is that when you push current->right on the stack, you might have on the stack some nodes for which the left child was already visited, while other nodes on the stack still need their left child to be visited.

An example may illustrate the problem. Let's take this tree with just two nodes:

           1
          /
         2

Iteration 1: current has node 1. As there is a left child (2), this node is added on the stack, which now has nodes 1 and 2.

Iteration 2: current has node 2. Now there is no left child, so the value 2 is output to ans, and the node is popped from the stack.

Iteration 3: this iteration starts with exactly the same stack state as when the first iteration started: current is 1 and again its left child is pushed on the stack. This leads to an infinite loop.

The problem is that there can be nodes on the stack whose left child has already been on the stack and should not be stacked again. In case you have such a node on the top of the stack, you should not go to a next iteration of the loop yet, because that will lead to the above problem.

To solve this, consider that when you have output a value to ans, all nodes on the stack have already pushed their left child on the stack. We can pop such a node and also output its value to ans, and continue like that until we get to a node that has a right child. In that case we should push that right child (the code you already have), and that is a node that still needs its left child to be visited, so now it is safe to continue with an iteration of the main loop.

In short, the correction is to add an inner loop to your code:

    vector<int> inorderTraversal(TreeNode* root) {
        vector<TreeNode*> stack;
        vector<int> ans;

        if(root){
            stack.push_back(root);
        }


        while(!stack.empty()){
            TreeNode* current = stack.back();
            if(current->left){
                stack.push_back(current->left);
                continue;                 
            }

            ans.push_back(current->val);
            stack.pop_back(); 

            // Unwind the stack until a right child is found:
            while (!current->right && !stack.empty()) {
                current = stack.back();
                ans.push_back(current->val);
                stack.pop_back();
            }

            if (current->right) {
                stack.push_back(current->right);
            }
        }

        return ans;
    }