Share my several C++ solutions,easy to understand

• (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;
}
};``````

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