【代码随想录】——“二叉树的递归遍历”

每次写递归，都按照这三要素来写

1. 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。

2. 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。

3. 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

 144. 二叉树的前序遍历

确定递归函数的参数和返回值：因为要打印出前序遍历节点的数值，所以参数里需要传入vector再放节点的数值，除了这一点就不需要在处理什么数据了也不需要有返回值，所以递归函数返回类型就是void 。所以传入的参数就是root和res，不需返回值。

确定终止条件：就是遇到空节点的时候，return即可

确定单层递归的逻辑：前序遍历是根左右

class Solution {
public:
    void Traversal(TreeNode* cur,vector &rescur){
        if(cur==NULL) return;//终止条件
        //单层循环
        rescur.push_back(cur->val);//根
        Traversal(cur->left,rescur);//左
        Traversal(cur->right,rescur);//右
    }
    vector preorderTraversal(TreeNode* root) {
        vector res;
        Traversal(root,res);
        return res;
    }
};

145. 二叉树的后序遍历  

class Solution {
public:
    void Traversal(TreeNode* cur,vector &rescur){
        if(cur==NULL) return;//终止条件
        //单层循环
        Traversal(cur->left,rescur);//左
        Traversal(cur->right,rescur);//右
        rescur.push_back(cur->val);//根
    }

    vector postorderTraversal(TreeNode* root) {
        vector res;
        Traversal(root,res);
        return res;
    }
};

94. 二叉树的中序遍历 

class Solution {
public:
    void Traversal(TreeNode* cur,vector &rescur){
        if(cur==NULL) return;//结束条件
        //单层循环
        Traversal(cur->left,rescur);//左
        rescur.push_back(cur->val);//根
        Traversal(cur->right,rescur);//右

    }
    vector inorderTraversal(TreeNode* root) {
        vector res;
        Traversal(root,res);
        return res;
    }
};

 以上前后中序遍历，都是用递归的方法，确定递归的传递参数和返回值之后，确定递归结束条件，单层循环就是前后中序遍历的顺序（根左右这些）