递归三部曲

1. 确定递归函数的参数和返回值

2. 确定终止条件

3. 确定单层递归的逻辑

中序遍历

• 前中后序遍历，就是修改下面三者的代码位置

前：travelsal(cur->left,result);​

中：result.push_back(cur->val);​

后：travelsal(cur->right,result);​

#include <vector>

using namespace std;

struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode() : val(0), left(nullptr), right(nullptr) {}
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  };

class Solution {
public:

    void travelsal(TreeNode* cur,vector<int>& result)
    {
        if(cur == nullptr)
        {
            return;
        }

        travelsal(cur->left,result);
        result.push_back(cur->val);
        travelsal(cur->right,result);
    }

    vector<int> inorderTraversal(TreeNode* root) {

        vector<int> result;
        travelsal(root,result);
        return result;
    }
};