Solve this problem using recursive and iterative way.


  • 0
    G

    When we pre order a binary tree, we usually use two ways to solve this problem, recursive and iterative way.

    Recursive way:

    class Solution {
    public:
        vector<int> vec;
        
        vector<int> preorderTraversal(TreeNode *root) {
            if(!root)
                return vec;
            preorder(root);
            return vec;
        }
        void preorder(TreeNode *root){
            if(root){
                vec.push_back(root->val);
                preorder(root->left);
                preorder(root->right);
            }
        }
    };
    

    Iterative way using stack:

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

Log in to reply
 

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