Binary Tree Preorder Traversal
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<int> preorderTraversal（TreeNode *root） {
vector<int> prePath;
preStack（root, prePath）；
return prePath;
}
递归法：
[cpp]
void preNodes（TreeNode *node,vector<int> &onePath）
{
if（node == nullptr） return;
onePath.push_back（node->val）；
preNodes（node->left, onePath）；
preNodes（node->right, onePath）；
}
非递归法：
[cpp]
void preStack（TreeNode *node, vector<int> &prePath）
{
if（node == nullptr） return;
stack<TreeNode *> 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
} |