Share my several C++ solutions,easy to understand


  • 1
    V

    (1)Recursion

    class Solution {
    public:
        vector<int> preorderTraversal(TreeNode* root) {
            vector<int> ret;
            myPreorderTraversal(root, ret);
            
            return ret;
        }
        void myPreorderTraversal(TreeNode *root, vector<int> &vec)
        {
            if (root == NULL)
                return;
                
            vec.push_back(root->val);
            
            myPreorderTraversal(root->left, vec);
            myPreorderTraversal(root->right, vec);
        }
    };
    

    (2)Iterative solution using stack

    class Solution {
    public:
        vector<int> preorderTraversal(TreeNode* root) {
            vector<int> ret;
            stack<TreeNode *> s;
            TreeNode *node = root;
            
            if (root == NULL) return ret;
            
            while (node)
            {
                while(node)
                {
                    s.push(node);
                    ret.push_back(node->val);
                    node = node->left;
                }
                while (node == NULL && !s.empty())
                {
                    node = s.top();//once a node occurs in the stack,meaning that the node had been visited
                    s.pop();
                    node = node->right;
                }
            }
            
            return ret;
        }
    };
    

    (3)Another way of writing

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

Log in to reply
 

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