代码解决

这段代码实现了二叉树的前序遍历，前序遍历的顺序是：访问根节点 -> 递归遍历左子树 -> 递归遍历右子树。以下是详细解释，包括各个部分的注释：

// 二叉树节点的定义
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 traversal(TreeNode* tree, vector<int>& res)
    {
        if(tree == NULL) return;            // 如果节点为空，则直接返回
        res.push_back(tree->val);           // 访问根节点，将节点值加入结果向量
        traversal(tree->left, res);         // 递归遍历左子树
        traversal(tree->right, res);        // 递归遍历右子树
    }

    // 前序遍历的主函数
    vector<int> preorderTraversal(TreeNode* root) 
    {
        vector<int> result;                 // 存储遍历结果的向量
        traversal(root, result);            // 调用递归函数进行前序遍历
        return result;                      // 返回结果向量
    }
};

详细解释

1. TreeNode 结构体：

   • 定义了一个二叉树节点结构体TreeNode，包括节点的值val，左子节点指针left，和右子节点指针right。
   • 提供了三种构造函数：
     • 默认构造函数初始化节点值为0，左右子节点为空。
     • 带一个整数参数的构造函数初始化节点值为给定值，左右子节点为空。
     • 带一个整数和两个子节点参数的构造函数初始化节点值和左右子节点。

2. Solution 类：

   • 包含前序遍历二叉树的实现。

3. traversal 函数：

   • 这是一个递归函数，用于执行前序遍历。
   • 参数tree是当前节点，res是存储遍历结果的向量。
   • 首先检查当前节点是否为空，如果为空，则返回。
   • 然后将当前节点的值加入结果向量。
   • 接下来递归遍历左子树和右子树。

4. preorderTraversal 函数：

   • 这是前序遍历的主函数。
   • 创建一个空的结果向量result。
   • 调用递归函数traversal从根节点开始进行前序遍历。
   • 最后返回结果向量。

前序遍历的顺序

在前序遍历中，首先访问根节点，然后递归遍历左子树，最后递归遍历右子树。例如，给定以下二叉树：

使用场景

前序遍历常用于：

• 复制二叉树
• 计算二叉树节点的数量
• 前序表达式的求值
• 将二叉树转换为其他数据结构