Easy C++ solution using Stack


  • 32
    Y
    class Solution {
    public:
    vector<int> preorderTraversal(TreeNode *root) {
        if (root==NULL) {
            return vector<int>();
        }
        vector<int> result;
        stack<TreeNode *> treeStack;
        treeStack.push(root);
        while (!treeStack.empty()) {
            TreeNode *temp = treeStack.top();
            result.push_back(temp->val);
            treeStack.pop();
            if (temp->right!=NULL) {
                treeStack.push(temp->right);
            }
            if (temp->left!=NULL) {
                treeStack.push(temp->left);
            }
        }
        return result;
    }
    };

  • -6
    N

    here is mine code:

     class Solution {
        public:
            vector<int> preorderTraversal(TreeNode* root) {
                vector<int> res;
                // _preorderTraversalRecursive(root, res);
                _preorderTraversalNonRecursive(root, res);
                return res;
            }
            
            void _preorderTraversalNonRecursive(TreeNode* root, vector<int> &res)
            {
                if(root == NULL)
                    return;
                stack<TreeNode*> stack;
                stack.push(root);
                while (!stack.empty()) {
                    TreeNode* n_ptr = stack.top();
                    while (n_ptr->left) {
                        res.push_back(n_ptr->val);
                        stack.push(n_ptr->left);
                        n_ptr = n_ptr->left;
                    }
                    res.push_back(n_ptr->val);
                    n_ptr = stack.top();
                    do{
                        n_ptr = stack.top();
                        stack.pop();
                    }while (n_ptr->right == NULL && !stack.empty());
                    if(n_ptr->right)
                        stack.push(n_ptr->right);
                    
                }
                
            }
            
            void _preorderTraversalRecursive(TreeNode* root, vector<int> &res)
            {
                if(root == NULL)
                    return;
                res.push_back(root->val);
                if(root->left)
                    _preorderTraversalRecursive(root->left, res);
                if(root->right)
                    _preorderTraversalRecursive(root->right, res);
            }
        };

  • 0
    R

    No need to define a new pointer for temp. You can use root in your while loop as well.


Log in to reply
 

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