Leetcode:二叉树无序Traversal.problem:Memory有限公司

Question

下面的代码按照顺序执行二进制树遍历。当我在Leetcode中执行它时，我会收到一个Run Status Code: Memory Limit Exceeded。有人能解释一下是什么导致了这个错误吗？

   vector<int> inorderTraversal(TreeNode* root) {

    vector<int> res;
    if(root==NULL)
        return res;
    stack<TreeNode*> st;
    st.push(root);
    while(st.empty()==0){
        TreeNode* cur=st.top();
        st.pop();
        if(cur->right!=NULL)//right childtree is not NULL,push
            st.push(cur->right);
        if(cur->left!=NULL){//left childtree is not NULL,push
            st.push(cur);
            st.push(cur->left);
        }
        else       //if left child tree is NULL,store the value
            res.push_back(cur->val);

    }

    //inorder(root,res);
    return res;
}

​

​

Answer 1

如果左子节点为null，则代码仅将值存储到结果堆栈中。

但是，对于您的示例，节点2左子节点从未设置为null，因此它从未插入结果堆栈，而是插入到st堆栈中。如果打印出输出，您可以观察到3被插入到一个循环中，从而导致内存问题。

跟踪祖先的可能策略：

• 检查一下琐碎的情况。
• 准备一个堆栈来保存祖先，另一个来保存结果。
• 当堆栈是非空的，或者如果根不是空的，
  • 如果根不是null：
    • 将根插入到祖先堆栈。
    • 将根更新为根的左子，可能为null。

​

- if the root is null (meaning dead end from the left)  
    - visit the stack, pop the top element to be the root. 
    - add the root to the result stack
    - assign the right child of the root to be the root, possibly to be a null.

​

​