Given a binary tree, return the preorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},
1
\
2
/
3
return [1,2,3].
Note: Recursive solution is trivial, could you do it iteratively
的确如note说的一样，使用递归只需要几分钟就解决了，如果不是用递归，自己琢磨的话还是花了差不多半个小时。
看代码就知道非递归比递归长很多。
非递归方法主要难点：
1. 需要使用两个循环，左子树循环嵌套右子树循环；
2. 有右子树的时候，需要跳出本循环，让其重新进入左子树循环。
2. 无左子树的时候，需要出栈，而不是等到空子树才出栈。
下面使用两种方法解决一下这个题目，他们的时间效率都差不多，都是12ms，大概测试数据都很少，所以时间都一样。也是LeetCode上的一个水题了，测试数据都不多。
主函数都是一样的：
[cpp]
vector preorderTraversal(TreeNode *root) {
vector prePath;
preStack(root, prePath);
return prePath;
}
递归法：
[cpp]
void preNodes(TreeNode *node,vector &onePath)
{
if(node == nullptr) return;
onePath.push_back(node->val);
preNodes(node->left, onePath);
preNodes(node->
right, onePath);
}
非递归法：
[cpp]
void preStack(TreeNode *node, vector &prePath)
{
if(node == nullptr) return;
stack stk;
TreeNode *cur = node;
stk.push(cur);
while (!stk.empty())
{
cur = stk.top();
prePath.push_back(cur->val);
while (cur->left)
{
prePath.push_back(cur->left->val);
cur = cur->left;
stk.push(cur);
}
stk.pop();
while (!stk.empty() || cur->right)
{
if(cur->right)
{
cur = cur->right;
stk.push(cur);
break;
}
else
{
cur = stk.top();
stk.pop();
}
}//while
}//while
}