4ms C++ solution with std::stack


  • 0
    Z

    I use a stack to replace the recursion. During the iterations, each treenode is given a state. State being 0 means we need to traverse its left child and state being 1 means we have traversed its left and now need to traverse itself and its right child.

    class Solution {
        struct traverseNode
        {
            TreeNode* Node;
            int State; // 0: need to traverse left child; 1: need to traverse right child
            traverseNode(TreeNode* pNode, int state) : Node(pNode), State(state) { }
            ~traverseNode() { }
        };
        
    public:
        vector<int> inorderTraversal(TreeNode* root) {
            vector<int> ans = vector<int>();
            if (!root) return ans;
            stack<traverseNode*> stk;
            stk.push(new traverseNode(root, 0));
            
            while (!stk.empty())
            {
                traverseNode* pnode = stk.top();
                if (pnode->State == 0) // has not traversed left child
                {
                    if (pnode->Node->left) // has left child
                    {
                        pnode->State = 1;
                        stk.push(new traverseNode(pnode->Node->left, 0));
                    }
                    else // has no left child
                    {
                        ans.push_back(pnode->Node->val);
                        stk.pop();
                        if (pnode->Node->right) // has right child
                        {
                            stk.push(new traverseNode(pnode->Node->right, 0));
                        }
                        delete pnode;
                    }
                }
                else // has traversed left child
                {
                    ans.push_back(pnode->Node->val);
                    stk.pop();
                    if (pnode->Node->right) // has right child
                    {
                        stk.push(new traverseNode(pnode->Node->right, 0));
                    }
                    delete pnode;
                }
            }
            return ans;
        }
    };
    

Log in to reply
 

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