题意：给一棵树，求其先根遍历的结果。
思路：
（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) {
if(!root) return vector<int>();
vector<int> ans(,root->val);
vector<int> tmp=preorderTraversal(root->left);
ans.insert(ans.end(),tmp.begin(),tmp.end());
tmp=preorderTraversal(root->right);
ans.insert(ans.end(),tmp.begin(),tmp.end());
return ans;
} };
AC代码
（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> ans;
void DFS(TreeNode* t)
{
if(!t) return;
ans.push_back(t->val);
DFS(t->left);
DFS(t->right);
}
vector<int> preorderTraversal(TreeNode* root) {
DFS(root);
return ans;
}
};
AC代码
（3）迭代法：
/**
* 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) {
if(!root) return vector<int>(); stack<pair<TreeNode*,int>> stac;
stac.push(make_pair(root,));//第二个参数用于记录其已经遍历了左/右孩子
vector<int> ans;
while( !stac.empty() )
{
TreeNode* cur=stac.top().first;
if( stac.top().second== ) ans.push_back(cur->val); if(cur->left && stac.top().second==)//没有遍历过孩子的进来
{
cur=cur->left;
stac.top().second=;
stac.push(make_pair(cur,));
}
else if(cur->right && stac.top().second<)//遍历过左孩子或者没有左孩子的才进来
{
cur=cur->right;
stac.top().second=;
stac.push(make_pair(cur,));
}
else stac.pop();//以上两个都进不去，要么遍历完，要么没有孩子
}
return ans;
}
};
AC代码
（4）更叼的迭代法：
/**
* 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) {
if(!root) return vector<int>(); vector<int> ans;
stack<TreeNode *> stac;
stac.push(root); while( !stac.empty() )
{
TreeNode *t=stac.top();
ans.push_back(t->val);
stac.pop();//只需要孩子都压栈，父亲无用
if(t->right) stac.push(t->right);
if(t->left) stac.push(t->left);
}
return ans;
}
};
AC代码