题目链接：144. 二叉树的前序遍历
题目：
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例1：
输入：root = [1,null,2,3]
输出：[1,2,3]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
示例 4：
输入：root = [1,2]
输出：[1,2]
示例 5：
输入：root = [1,null,2]
输出：[1,2]
提示：
- 树中节点数目在范围 [0, 100] 内
- -100 <= Node.val <= 100
进阶：递归算法很简单，你可以通过迭代算法完成吗？
思路和算法：
这题二叉树的前序遍历采用递归法很简单，只要明确递归三要素就可以很快的解出来，具体三要素讲解可以见：教你写递归——递归三部曲。
在这题中，三要素分别为：
（1）确定递归函数的参数和返回值：因为要打印出前序遍历节点的数值，所以参数里需要传入vector在放节点的数值，除了这一点就不需要在处理什么数据了也不需要有返回值，所以递归函数返回类型就是void；
即：void traversal(TreeNode* cur, vector< int >&res) {}
（2）确定终止条件：在递归的过程中，如何算是递归结束了呢，当然是当前遍历的节点是空，那么本层递归就要要结束了，所以如果当前遍历的这个节点是空，就直接return；
即：if (cur == NULL) return;
（3）确定单层递归的逻辑：前序遍历是中左右的顺序，所以在单层递归的逻辑，是要先取中节点的数值放入结果数组后递归左右子二叉树；即：
res.push_back(cur->val); // 中 traversal(cur->left, res); // 左 traversal(cur->right, res); // 右
代码（c++）：
//递归
class Solution {
public:
vector preorderTraversal(TreeNode* root) {
vector res;
traversal(root, res);
return res;
}
private:
void traversal(TreeNode* cur, vector& res) {
if (!cur) return; //结束条件：当前节点为空
res.push_back(cur->val); //中
traversal(cur->left, res); //左
traversal(cur->right, res); //右
}
};
关于进阶里的问题，采用迭代法。
代码（c++）：
前序遍历是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。
为什么要先加入右孩子，再加入左孩子呢？ 是因为栈是先进后出的特点，这样出栈的时候才是中左右的顺序。
//迭代
class Solution {
public:
vector preorderTraversal(TreeNode* root) {
vector res; //结果数组
if (!root) return res;
stack stk;
stk.push(root);
//当栈stk里有数据
while (!stk.empty()) {
TreeNode* cur = stk.top(); //栈顶元素<==>中值
stk.pop(); //弹出栈顶元素
res.push_back(cur->val); //将中值添加到结果数组
if(cur->right) stk.push(cur->right); //将右子树压入栈中
if(cur->left) stk.push(cur->left); //将左子树压栈
}
return res;
}
};
在这里强调一点，就是需要栈节点不为空再压栈，因为空指针和数据元素一样能够进栈。并且如果栈原来为空，压入空指针后栈就不会为空了。空指针一旦被赋予指针，如果是在32位机上则占四个字节。只不过是没有指向堆内存中的任何数据。而空指针已经压进栈了，不加以释放就一直存在。
