题目：
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?
代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ret_l, ret_r;
if ( root ){
ret_l = Solution::preorderTraversal(root->left);
ret_l.insert(ret_l.begin(), root->val);
ret_r = Solution::preorderTraversal(root->right);
ret_l.insert(ret_l.end(), ret_r.begin(), ret_r.end());
}
return ret_l;
}
};
tips：
trivial的递归版
===================================
再来一个non trivial的迭代版
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ret;
if ( !root ) return ret;
stack<TreeNode*> sta;
sta.push(root);
while ( !sta.empty() )
{
TreeNode *tmp = sta.top();
sta.pop();
ret.push_back(tmp->val);
if (tmp->right) sta.push(tmp->right);
if (tmp->left) sta.push(tmp->left);
}
return ret;
}
};
tips:
把递归调用改成人工堆栈：
1. 把根节点压进栈
2. 栈定元素出栈，把val加入到ret中
3. 注意：先压right入栈，再压left入栈（保证压入栈的元素都是非NULL）
循环1~3，直到栈空。
==============================================
还有更高端一些的Morris遍历算法：特点是空间复杂度是O(1)
http://www.cnblogs.com/AnnieKim/archive/2013/06/15/morristraversal.html
=================================================
第二次过这道题，只写了一个递归的。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root)
{
vector<int> ret;
Solution::traversal(ret, root);
return ret;
}
static void traversal(vector<int>& ret, TreeNode* root)
{
if (!root) return;
ret.push_back(root->val);
Solution::traversal(ret, root->left);
Solution::traversal(ret, root->right);
}
};