Leetcode: двоичное древовидное заграждение 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

Ваш код сохраняет значение в стеке результатов только в том случае, если левый дочерний узел является нулевым.

Однако, для вашего примера, узел 2 левого дочернего узла никогда не устанавливается в нуль и, следовательно, он никогда не вставляется в стек результатов, но он находится в стеке st. Если вы распечатываете свои выходные данные, вы можете заметить, что 3 вставлен в цикл, что вызывает проблему с памятью.

Возможная стратегия для отслеживания предка:

• Проверка на тривиальный случай.
• Подготовьте стек, чтобы сохранить предков, и один, чтобы сохранить результат.
• Пока стек не пустой или корень не нулевой
  • если корень не равен нулю:
    • вставить корень в стек предков.
    • обновить корень, чтобы он стал левым потомком корня, возможно, будет нулевым.
  • если корень нулевой (имеется в виду тупик слева)
    • зайдите в стек, вставьте верхний элемент в корень.
    • добавить корень в стек результатов
    • присваивает правому дочернему элементу корня корень, возможно, равный нулю.