【2024考研】题解15 | #二叉树的前中后序遍历#

【写在前面】——参与一个话题#我的求职思考#。

①一场秋雨一场寒，快考研预报名了，身边保研的同学已经有着落了，网上有所谓“缩招”标签，这不经给考研党们一丝寒意。

②前不久图书馆有几位同学因为座位归属吵起来差点动手，大家现在仿佛都是“易燃易爆炸”的液化气罐，里面充满焦虑牌液化气。

③今天无意我刷到张雪峰老师直播里的一句“你该考上的就会考上，该考不上就还是考不上，管什么缩招扩招！”

④还有“李佳琦花西子直播事件”，我又想起了翻版梗——“xx大学很不容易的，这~么多年一直以来都是这个分数线，有时候想一想自己的问题好不好，这几年有没有好好学习~”

⑤焦虑，来源于想得太多，做的太少，我想这也适用于求职吧。

最后引用我鼠标垫上毛主席的一句话：“丢掉幻想，准备斗争”！

#include <vector>
class Solution {
public:
    vector<int> MENG;
    void dfs(TreeNode *TNode){
        if(TNode == nullptr) return ;
        dfs(TNode->left);
        dfs(TNode->right);
        ans.push_back(TNode->val);
    }
    vector<int> postorderTraversal(TreeNode* root) {
        // write code here
        dfs(root);
        return MENG;
    }
};

#include <vector>
class Solution {
public:
    vector<int> XIANG;
    void dfs(TreeNode *node){
        if(node == NULL) return ;
        dfs(node->left);
        res.push_back(node->val);
        dfs(node->right);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        // write code here
        dfs(root);
        return XIANG;
    }
};

#include <vector>
class Solution {
public:
vector<int> YANG;
    void dfs(TreeNode *Node){
        if(Node == nullptr) return ;
        res.push_back(Node->val);
        dfs(Node->left);
        dfs(Node->right);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        // write code here
        dfs(root);
        return YANG;
    }
};

关键是分清楚遍历顺序——前序、中序、后序。

前序遍历、中序遍历和后序遍历是二叉树的三种遍历方式。

它们的时间复杂度和空间复杂度都是O(n)，其中n是二叉树中节点的数量。

• 前序遍历：先访问根节点，然后递归地遍历左子树，最后递归地遍历右子树。
• 中序遍历：先递归地遍历左子树，然后访问根节点，最后递归地遍历右子树。
• 后序遍历：先递归地遍历左子树，然后递归地遍历右子树，最后访问根节点。

基本算法思想如下：

1. 前序遍历的基本算法思想是先访问根节点，然后递归地遍历左子树和右子树。具体实现可以使用递归或者栈来实现。
2. 中序遍历的基本算法思想是先递归地遍历左子树，然后访问根节点，最后递归地遍历右子树。具体实现可以使用递归或者栈来实现。
3. 后序遍历的基本算法思想是先递归地遍历左子树和右子树，然后访问根节点。具体实现可以使用递归或者栈来实现。

递归实现的代码比较简洁，但是可能会使用额外的系统栈空间。非递归实现的代码需要使用栈来保存节点，以模拟递归的过程，但是不会使用额外的系统栈空间。在非递归实现中，需要注意节点的访问顺序和出栈顺序，以及栈的使用方式。