My 8ms c++ solution, iterative


  • 0
    /**
     struct AuxNode {
         bool visited;
         TreeNode *node;
         AuxNode(TreeNode *root): node(root), visited(false) {}
     };
    class Solution {
    public:
        vector<int> inorderTraversal(TreeNode* root) {
            if (root == NULL)
                return {};
            vector<int> t_order;
            deque<AuxNode*> n_traverse;
            AuxNode* node = new AuxNode(root);
            n_traverse.push_front(node);
            bool all_visited = false;
            int i;
            while(!all_visited){
                for (i = 0; i < n_traverse.size(); ++i) {
                    AuxNode* node = n_traverse[i];
                    if (!node->visited) {
                        bool left_existed = false;
                        if (node->node->left) {
                            AuxNode *left = new AuxNode(node->node->left);
                            cout << "left node exists, value: " << left->node->val << endl;
                            n_traverse.insert(n_traverse.begin() + i, left);
                            left_existed = true;
                        }
                        if (node->node->right) {
                            int pos = left_existed == true ? i + 2 : i + 1;
                            AuxNode *right = new AuxNode(node->node->right);
                            cout << "right node exists, value: " << right->node->val << endl;
                            n_traverse.insert(n_traverse.begin() + pos, right);
                        }
                        node->visited = true;
                        break;
                    }
                }
                if (i == n_traverse.size())
                    all_visited = true;
                cout << n_traverse.back()->node->val << endl;
            }
            for (AuxNode *node : n_traverse) {
                t_order.push_back(node->node->val);
            }
            return t_order;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.