C++算法练习-day31——二叉树的前/中/后序遍历

题目来源：. - 力扣（LeetCode）

题目思路分析

题目要求实现二叉树的三种遍历方式：前序遍历、中序遍历和后序遍历，并以整数数组的形式返回遍历结果。每种遍历方式都有其特定的节点访问顺序：

• 前序遍历：根节点 -> 左子树 -> 右子树。
• 中序遍历：左子树 -> 根节点 -> 右子树。
• 后序遍历：左子树 -> 右子树 -> 根节点。

这些遍历方式对于理解二叉树的结构、构建二叉树的镜像、以及解决一些特定问题（如二叉搜索树的查找和排序）非常有用。

代码:

#include <vector>  
  
// 二叉树节点的定义（重复部分，实际使用时只需定义一次）  
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 PreorderSolution {  
public:   
    std::vector<int> PreorderTraversal(TreeNode* root, std::vector<int>& res) {  
        // 如果当前节点为空，直接返回当前结果数组  
        if (!root) {  
            return res;  
        }  
        // 访问当前节点，将值加入结果数组  
        res.push_back(root->val);  
        // 递归遍历左子树  
        PreorderTraversal(root->left, res);  
        // 递归遍历右子树  
        PreorderTraversal(root->right, res);  
        // 返回遍历结果  
        return res;  
    }  
    std::vector<int> preorderTraversal(TreeNode* root) {   
        std::vector<int> res;  
        return PreorderTraversal(root, res);  
    }  
};  
  
// 中序遍历的实现（类似地，这里也可以与前序遍历合并到一个类中，但为了清晰展示每种遍历方式，分开写）  
class InorderSolution {  
public:  
    std::vector<int> InorderTraversal(TreeNode* root, std::vector<int>& res) {  
        if (!root) {  
            return res;  
        }  
        // 递归遍历左子树  
        InorderTraversal(root->left, res);  
        // 访问当前节点，将值加入结果数组  
        res.push_back(root->val);  
        // 递归遍历右子树  
        InorderTraversal(root->right, res);  
        return res;  
    }  
    std::vector<int> inorderTraversal(TreeNode* root) {   
        std::vector<int> res;  
        return InorderTraversal(root, res);  
    }  
};  
  
// 后序遍历的实现  
class PostorderSolution {  
public:  
    std::vector<int> PostorderTraversal(TreeNode* root, std::vector<int>& res) {  
        if (!root) {  
            return res;  
        }  
        // 递归遍历左子树  
        PostorderTraversal(root->left, res);  
        // 递归遍历右子树  
        PostorderTraversal(root->right, res);  
        // 访问当前节点，将值加入结果数组  
        res.push_back(root->val);  
        return res;  
    }  
    std::vector<int> postorderTraversal(TreeNode* root) {   
        std::vector<int> res;  
        return PostorderTraversal(root, res);  
    }  
};

知识点摘要

1. 二叉树：一种树形数据结构，每个节点最多有两个子节点，称为左子节点和右子节点。
2. 遍历：按照某种规则访问树中所有节点的过程。
3. 前序遍历：根节点 -> 左子树 -> 右子树。
4. 中序遍历：左子树 -> 根节点 -> 右子树。
5. 后序遍历：左子树 -> 右子树 -> 根节点。
6. 递归：在函数内部调用自身的编程技巧，常用于解决可以分解为相似子问题的问题。

本文展示了如何使用递归实现二叉树的前序遍历、中序遍历和后序遍历。每种遍历方式都有其特定的节点访问顺序，这些顺序对于理解二叉树的结构和解决实际问题非常重要。通过递归，我们可以优雅地处理树形数据结构，将复杂问题分解为更小的子问题。希望这篇文章能帮助你更好地理解二叉树的遍历方式以及相关的编程技巧。在实际应用中，你可以根据需要选择合适的遍历方式来处理二叉树。