Given a binary tree, return the preorder traversal of its nodes' values.
Example:
Input:[1,null,2,3]
1
\
2
/
3 Output:[1,2,3]
Follow up: Recursive solution is trivial, could you do it iteratively?
-----------------------------------------------------------------------------------------------------------
二叉树的前序遍历（preorder traversal）。emmm，虽然题目要求用非递归，但是，我现在先用递归来写（简单）。emmmm，只要理解透递归的含义，解决这个问题是异常的简单。
C++代码：递归代码1：
/**
* 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> vec;
DFS(root,vec);
return vec;
}
void DFS(TreeNode* root,vector<int>& vec){
if(!root) return;
vec.push_back(root->val);
if(root->left) DFS(root->left,vec);
if(root->right) DFS(root->right,vec);
}
};
递归代码2：
/**
* 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> vec; //这个vec必须放在外面。否则，如果在里面的话，在这个样例中最后只得到一个含有一个数的数组。
vector<int> preorderTraversal(TreeNode* root) {
if(!root) return vec;
vec.push_back(root->val);
preorderTraversal(root->left);
preorderTraversal(root->right);
return vec;
}
};