Leetcode:Binary 树顺序 Traversal.problem: 超出内存限制

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

如果左 child 节点为空，您的代码仅将值存储到结果堆栈中。

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

跟踪祖先的可能策略：

检查小案例。
准备一叠保存祖先，一叠保存结果。
当堆栈为 non-empty 或者如果根不为空
- 如果根不为空：
  - 将根插入祖先堆栈。
  - 将根更新为根的左侧 child，可能为空。
- 如果根为空（表示从左边开始是死胡同）
  - 访问栈，弹出栈顶元素为根。
  - 将根添加到结果堆栈
  - 赋根的右child为根，可能为null。

Leetcode:Binary 树顺序 Traversal.problem: 超出内存限制

Leetcode:Binary Tree Inorder Traversal.problem:Memory Limited exceeded

binary-tree

memory-limit