0

Considering the Solution of Leetcode 94. Binary Tree Inorder Traversal. What confusing me is whether is is safe to access the node after the node being popped(stk.pop(); res.push_back(root->val);). I know that the underline container of std::stack is std::deque. And the pop() of std::stack is implemented by pop_back() of std::deque.

This program seems can be executed in the right way, I want to confirm,

  1. It is safe to access the popped node. Whether the pop() release the memory allocated by new operator.
  2. If the pop() reclaimed the memory, then whether the reason is that the container doesn't release storage immediately when element is popped.

Thanks!

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stk;
        while (root != nullptr || !stk.empty()) {
            while (root != nullptr) {
                stk.push(root);
                root = root->left;
            }
            root = stk.top();
            stk.pop();
            res.push_back(root->val);
            root = root->right;
        }
        return res;
    }
};

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/binary-tree-inorder-traversal/solution/er-cha-shu-de-zhong-xu-bian-li-by-leetcode-solutio/
amont
  • 81
  • 8
  • 2
    `pop` removes a **pointer** to the object from the stack, not the object itself. The objects pointed by the pointers are not deleted by the posted part of the code. Since you don't own the `TreeNode` objects (some LeetCode runtime stuff owns them), this does not cause memory leaks. – kotatsuyaki Jun 18 '22 at 10:23
  • Erasing someone's address from your address book does not cause their home to be demolished. – molbdnilo Jun 18 '22 at 12:10

0 Answers0