leetcode144. 二叉树的前序遍历
一、题目描述：
给你二叉树的根节点
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
三、先决知识点：
- 无
四、思路讲解：
4.1递归思路：
- 先判断当前节点是否为空。
- 如果为空，直接返回。
- 如果不为空，将节点值存储到vector中，递归当前节点的左子树和右子树。
4.2循环思路：
- 创建一个vector对象，用于返回。然后判断根节点是否存在，如果不存在直接返回vector对象。
- 主要思想是利用栈，将每个节点分为左边和右边处理。
- 先处理左边，从根节点开始，一直向下找最左节点。期间将所有左节点的指针压栈，将节点值存储到vector中。先忽略所有路径上的右节点。
- 找到最左节点后，开始出栈每一个左节点，处理左节点的右子树，期间将每一个右子树看作左节点来继续压栈。
- 如果右节点为空，说明当前左节点已经全部处理完成。出栈下一个左节点，循环即可。
- 最后，当栈的最后一个左节点被弹出，整个二叉树就被处理为了。
五、C++代码：
5.1递归实现：
vector<int> preorderTraversal(TreeNode* root){vector<int> v;preorder(root,v);return v;}void preorder(TreeNode* root,vector<int>& v){if(root==nullptr)return;v.push_back(root->val);preorder(root->left,v);preorder(root->right,v);}
5.2循环实现：
vector<int> preorderTraversal(TreeNode* root){vector<int> v;if(root==nullptr)return v;stack<TreeNode*> s;while(!s.empty()||root!=nullptr){while(root!=nullptr){v.push_back(root->val);s.push(root);root=root->left;}root=s.top();s.pop();root=root->right;}return v;}