My C++ solution (recursive and stack based non-recursive)


  • 4
    D
    For non-recursive, it is simple to use a stack, but just remember to push the right child before the left child  
      class Solution {
        public:
        /*
                //recursive solution
            void preorderVec(TreeNode *root, vector<int> &result)
            {
                if(root)
                {
                    result.push_back(root->val);
                    preorderVec(root->left, result);
                    preorderVec(root->right, result);
                }
            }
        
            vector<int> preorderTraversal(TreeNode *root) {
                vector<int> result;
                preorderVec(root, result);
                return result;
            }
        */    
            vector<int> preorderTraversal(TreeNode *root) {
                //non-recursive solution
                vector<int> result;
                stack<TreeNode *> nodeS;
                TreeNode *topS;
                if(root)
                {// if the tree is non-empty
                    nodeS.push(root); // push the root to the stack
        
                    while(!nodeS.empty())
                    {  
                        topS = nodeS.top();
                        nodeS.pop(); // remove the top node
                        // add right child first and then left child
                        if(topS->right)
                        {
                            nodeS.push(topS->right);
                        }
                        if(topS->left)
                        {
                            nodeS.push(topS->left);
                        }
                        
                        result.push_back(topS->val);
                    }
                }
                return result;
            }
        };

Log in to reply
 

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