Причина бесконечного L oop? (реализация итеративного обхода порядка) C ++

Question

Вопрос: итеративно реализовать Inorder Traversal.

Моя попытка: (приводит к бесконечному l oop, которое я не смог отладить) любая помощь или предложения приветствуются

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
#include <vector>
#include <stack>
#include <unordered_set>
using namespace std;

class Solution {
    
    public:
    
        vector<int> inorderTraversal(TreeNode* root) {
            
            //iterative sol:
            vector<int> sol;
            stack<TreeNode*> dfs;
            dfs.push(root);
            unordered_set<TreeNode*> visited;
            visited.insert({root});
            TreeNode* temp;
            
            while (!dfs.empty()) {
                
                if (dfs.top()->left != nullptr && visited.find(dfs.top()->left) == visited.end()) {
                    dfs.push(dfs.top()->left);
                    visited.insert({dfs.top()->left});
                }
                else {
                    sol.push_back(dfs.top()->val);
                    temp = dfs.top();
                    dfs.pop();
                    
                    if (temp->right != nullptr && visited.find(temp->right) == visited.end()) {
                        dfs.push(temp->right);
                        visited.insert({temp->right});
                    }
                }     
                          
            }
            
            return sol;
            
        }
};

РЕДАКТИРОВАТЬ: У меня нет спецификаций c внутренних определений TreeNode, но если вы хотите запустить проблему, проверьте: https://leetcode.com/problems/binary-tree-inorder-traversal/

Answer 1

Вот проблема:

dfs.push(dfs.top()->left);
visited.insert(dfs.top()->left);

Вы нажимаете в стек (тогда dfs.top() изменится), а затем обращаетесь к dfs.top()->left в следующей строке.

Answer 2

Вы изменяете стек в первой строке здесь

  dfs.push(dfs.top()->left);
  visited.insert({dfs.top()->left});

то, что вы хотите сделать, это отметить предыдущий dfs.top()->left как посещенный, но вы добавляете больше элементов поверх стека и таким образом, новый dfs.top() является другим.

Чтобы решить эту проблему, вы должны использовать сохранение предыдущего dfs.top()->left в другой переменной.

Лучше всего использовать переменную или объект над которым вы работаете, должен быть неизменяемым, поскольку стек не является неизменяемым, не используйте его top при вставке в него или выполнении некоторых других вычислений. Вместо этого сохраните требуемую переменную во что-то неизменяемое, например temp здесь

 temp = dfs.top();
 if (temp->left != nullptr && visited.find(temp->left) == visited.end()) {
    dfs.push(temp->left);
    visited.insert({temp->left});
  }
  else {
    sol.push_back(dfs.top()->val);
    dfs.pop();
                    
    if (temp->right != nullptr && visited.find(temp->right) == visited.end()) {
       dfs.push(temp->right);
       visited.insert({temp->right});
    }
  }

Answer 3

Для реализации итеративного обхода по порядку требуется всего 2 простых правила.

Если вы находитесь на узле X, то:

1. Если у X есть правильный дочерний элемент, затем переместитесь к правому дочернему элементу и проследуйте как можно больше левых ссылок, чтобы найти следующий узел.
2. В противном случае найдите ближайшего предка X справа, т. е. ближайшего предка, чье левое поддерево содержит X. Если такого предка нет, то все готово.

Если в вашем дереве нет родительских ссылок, тогда вам понадобится стек для хранения правильных предков, но нет необходимости в посещенный набор:

vector<int> inorderTraversal(TreeNode* tree) {
    vector<int> ret;
    stack<TreeNode *> nextParents;
    for(;tree; tree = tree.left) {
        nextParents.push(tree);
    }
    while(!nextParents.empty()) {
        tree = nextParents.pop();
        ret.push_back(tree->val);
        for(tree = tree.right; tree; tree = tree.left) {
            nextParents.push(tree);
        }
    }
    return ret;
}