leetcode 94 - 迭代方式dfs（中序搜索）

Question

我收到“超出内存限制”错误。 我不知道为什么我得到这个..

下面是我的代码

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;
}
};

我尝试过不使用“继续” 但还是出现问题

1. 不建议使用“继续”？
2. 为什么会出现内存超限的情况？

Answer 1

问题是，当您将

current->right

压入堆栈时，堆栈上可能有一些其左子节点已被访问过的节点，而堆栈上的其他节点仍需要访问其左子节点。

举个例子就可以说明问题。让我们看这棵只有两个节点的树：

           1
          /
         2

迭代 1：

current

有节点 1。由于有左子节点 (2)，因此该节点被添加到堆栈中，堆栈现在有节点 1 和 2。

迭代2：

current

有节点2。现在没有左子节点，因此值2被输出到

ans

，并且该节点从堆栈中弹出。

迭代 3：此迭代以与第一次迭代开始时完全相同的堆栈状态开始：

current

为 1，并且 再次 将其左子节点推入堆栈。这会导致无限循环。

问题是堆栈上可能存在其左子节点已经在堆栈上且不应该再次堆栈的节点。如果堆栈顶部有这样的节点，您不应该进入循环的下一次迭代，因为这将导致上述问题。

为了解决这个问题，请考虑当您向

ans

输出一个值时，堆栈上的所有节点都已将其左子节点压入堆栈。我们可以弹出这样一个节点，并将其值输出到

ans

，并继续这样，直到到达具有右子节点的节点。在这种情况下，我们应该推送该右子节点（您已经拥有的代码），并且 that 是一个仍需要访问其左子节点的节点，因此现在可以安全地继续主循环的迭代。

简而言之，修正就是在代码中添加一个内循环：

    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;
    }