leetcode144、145、94二叉树的前、中、后序遍历

本文主要讲解二叉树的前、中、后序遍历的要点与细节，按照步骤思考更方便理解 

c++代码如下，末尾

具体要点：
1. 首先我们要了解二叉树的前序，中序，后序的遍历顺序：
        前序：中 左 右

        中序：左 中 右

        后序：左 右 中

怎么记呢？其实“ 前 中 后 ”指的是根节点的位置

---

2. 本题主要就是按照遍历顺序把元素都存入数组中，返回这个数组

---

3. 遇到二叉树的问题，特别是前中后序遍历时，其实核心是要使用深度优先算法

但若遇到层序遍历时，需要使用广度优先算法

---

4. 本题主要是深度优先算法，即递归

        我们下面用前序遍历举例说明：

        既然涉及递归，那么我们在写递归函数时，要确定以下内容：

• 确定递归参数与返回值
• 确定终止条件
• 确定单层递归逻辑

首先，我们考虑一下递归参数，二叉树递归中，一般都是要传递当前节点进去，这道题还需要我们传递数组进去（如果一时间考虑不清楚参数有什么，可以边写边加）

其次，考虑返回值，由于我们是直接操作的数组，所以我们不需要返回值，即void

然后，考虑终止条件，对于二叉树，一般的终止条件是遇到节点是null，就结束

最后，考虑单层递归逻辑，我们目的是把节点按照所要求的遍历顺序加入数组中，所以，遇到根节点就加入，左右节点就执行递归。（只要根据前中后序顺序排列一下逻辑即可）

---

总结

二叉树的遍历通常要利用递归操作来实现，对于递归我们要考虑好递归的参数、终止条件、逻辑，不要一直往深了想，企图把递归走一遍。只要把单层递归的细节搞清楚就好。

前序c++

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        //定义返回值
        vector<int> res;
        traversal(root,res);
        return res;
    }
    //确定递归函数的参数与返回值,没有返回值，直接操作的res
    void traversal(TreeNode* cur, vector<int>& res) {
        //确定终止条件，当遇到null时候就不执行递归了
        if (cur == nullptr) return;
        //前序遍历：中左右
        //先将根节点加入结果中
        res.push_back(cur->val);
        //左
        traversal(cur->left, res);
        //右
        traversal(cur->right, res);
    }
};

前序java

class Solution{
    public List<Integer> preorderTraversal(TreeNode root){
        List<Integer> res = new ArrayList<Integer>();
        Traversal(root, res);
        return res;
    }
    public void Traversal(TreeNode root, List<Integer> res){
        if(root == null) return;
        res.add(root.val);
        Traversal(root.left, res);
        Traversal(root.right, res);
    }
}

中序c++

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        function(root, res);
        return res;
    }
private:
    void function(TreeNode* root, vector<int>& res){
        if(!root){
            return;
        }
        function(root->left,res);
        res.push_back(root->val);
        function(root->right,res);
    }
};

 中序java

class Solution{
    public List<Integer> preorderTraversal(TreeNode root){
        List<Integer> res = new ArrayList<Integer>();
        Traversal(root, res);
        return res;
    }
    public void Traversal(TreeNode root, List<Integer> res){
        if(root == null) return;
        Traversal(root.left, res);
        res.add(root.val);
        Traversal(root.right, res);
    }
}

后序c++

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        traversal(root,res);
        return res;
    }
    void traversal(TreeNode* root,vector<int>& res){
        if (root == nullptr) return;
        
        traversal(root->left, res);
        traversal(root->right, res);
        res.push_back(root->val);
    }
};

后序java

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        traverse(root, res);
        return res;
    }
    public void traverse(TreeNode root, List<Integer> res) {
        if(root == null) return;
        traverse(root.left, res);
        traverse(root.right, res);
        res.add(root.val);
    }
}