题目要求
给定一个二叉树，返回前序遍历的结果。
注：尝试用递归和迭代两种方法。
类似题目：
解答：leetcode 94. Binary Tree Inorder Traversal (二叉树的中序遍历，递归法，非递归法)
示例
/* Example */
Input: [1,null,2,3]1\2/3Output: [1,2,3]
解题思路
什么是前序遍历？
前：指的是根节点出现的位置，以一个简单的树型结构举例，对树中的每个节点，在遍历的时候都按照先遍历根结点，中间遍历左孩子节点，最后遍历右孩子。
(结果为: 2-3-1)。
2/ \3 1
以此类推，我们可以知道中序遍历是先遍历左孩子节点，中间遍历根节点，最后是右孩子。（结果为：3-2-1）
后序遍历是：先遍历左孩子，中间是右孩子，最后是根节点。（结果为：3-1-2）
怎么实现前序遍历？
1、递归
递归方法是解决树类问题中常用的方法，易于理解，在解答本题的时候，我们根据上面讲的前序遍历方法，能写出如下的代码：
/*vector <int> preorder; // 保存节点的值。 */
vector<int> preorderTraversal(TreeNode* root) {
preorder.push_back(root->val);preorderTraversal(root->left);preorderTraversal(root->right);}
递归主要代码（c++）
/*** 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 != NULL) // 如果当前节点非空，那么执行递归。{
preorder.push_back(root->val); //先输出根节点preorderTraversal(root->left); // 然后遍历左孩子preorderTraversal(root->right); // 最后是右孩子}return preorder; }
private:vector<int>preorder;
};
2、 迭代法（非递归）
由于递归实现树的遍历非常简单，所以在面试的时候，面试官通常会不让我们用递归来做，所以这里我们介绍一下非递归实现树的遍历。需要借助 栈 这个数据结构来实现。
我们来想一下，前序遍历的要点是根节点出现在开始的位置（先根后左最后右）。
我们如何利用栈的特性（先进后出）来实现这个关系呢？
step1. 对一个二叉树(如下图)，我们首先要做的是从根开始 首先保留下根节点，然后遍历其左孩子，直到叶子节点4（再无左孩子为止）。
期间遍历到的所有节点都要进栈。最后再去遍历右孩子即。
现在栈内有2，3，4。栈顶元素是4。
（和中序遍历只有一行代码的不同，因为要先保存根结节点的值，可以相互参考领会）
2/ \ | |3 1 | 4 | --->stack.top()/ / \ | 3 |
*4 5 6 | 2 |———————— 已经打印保存的有：2-3-4tree stack
step2.由于在上一步，我们一路保存了根节点的值，并且到了叶子结点，所已根据前序遍历的顺序关系，下一步我们就需要遍历右孩子节点，如何指向右孩子呢？这是我们就需要栈的操作，来让我们从叶子节点回溯到双亲节点（也就是到根结点），所以要进行出栈操作，把指针指向栈顶元素。
（由于要取栈的栈顶元素操作，所以这个循环的条件之一就是保持栈非空！！可以看代码理解）
step3. 根据遍历的顺序，最后该遍历右孩子结点，我们只需要将现在的指针指向右侧孩子结点即可。
时间复杂度O(n),每个节点都遍历一次， 空间复杂度O(n)要存一个树形结构。
非递归主要代码–AC 0ms（c++）
/*** 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) {
TreeNode *p = root;stack<TreeNode *>s;vector<int>nodes;while(!s.empty() || p) // 循环条件节点和栈非空{
if(p){
nodes.push_back(p->val); //这里和中序不一样，先保存根节点s.push(p);p = p->left; // 再继续遍历左孩子节点}else{
p = s.top(); // 当 到了叶子结点的时候，需要借助出栈操作找到双亲。s.pop(); p=p->right;//然后遍历右孩子节点。}} return nodes;}
};
总结一下
和二叉树的中序遍历一样，在实现非递归排序的时候，我们利用栈的特性，帮助我们十分高效的完成任务，需要注意的点有：
-
循环条件的设置，保证当前节点和栈的非空性十分重要，否则很大可能会Runtime error.
-
牢记栈的操作，push 进， pop 出（先要指向top()）
-
特别推荐前序遍历和中序遍历一起来学习，实现过程相似。
解答：leetcode 94. Binary Tree Inorder Traversal (二叉树的中序遍历，递归法，非递归法)