1 题目解析

题目链接：二叉树的前序遍历

题目描述如下：

先回顾一下，二叉树的前序遍历的过程是：先遍历根，再遍历左子树，最后遍历右子树。 所以顺序就是：根，左子树，右子树

理清之后，继续回到之前的三步：

第一步：挖掘出相同的子问题  （关系到具体函数头的设计）
第二步：只关心具体子问题做了什么  （关系到具体函数体怎么写，是一个宏观的过程）
第三步：找到递归的出口，防止死递归  （关系到如何跳出递归）

相同的子问题：遍历根，左子树，右子树
递归的出口：当根为空的时候递归就退出
具体的子问题做了什么：遍历根，接下来的事情交给左子树，再交给右子树

函数头该如何写？

下面是leetcode提供的接口：

    vector<int> preorderTraversal(TreeNode* root) {}

可以看到传递的参数是TreeNode* root, 而vector<int>是返回值。所以我们函数头的参数必须包含两个，分别是TreeNode* root和vector<int>类型的参数。

例如下面这样：

void preorder(TreeNode* root, vector<int> &res)

函数体该如何写？

如何写函数体，就需要关心具体的操作过程。在二叉树的前序遍历上，具体的过程就是：先遍历根，再遍历左子树，最后遍历右子树。

函数的实现：

void preorder(TreeNode* root, vector<int> &res){//递归的出口if (root == nullptr)return;//1.遍历根res.push_back(root->val);//2.遍历左子树preorder(root->left, res);//3.遍历右子树preorder(root->right, res);}

2 总结

全部的代码如下：

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> res;preorder(root, res);return res;}//函数的具体操作void preorder(TreeNode* root, vector<int> &res){//递归的出口if (root == nullptr)return;//1.遍历根res.push_back(root->val);//2.遍历左子树preorder(root->left, res);//3.遍历右子树preorder(root->right, res);}
};