当前位置：首页 > article >正文

Leetcode 二叉树中根遍历

article 2024/11/15 15:18:31

在这里插入图片描述

采用递归算法，并且用一个向量来存储节点值。

算法C++代码如下：

/**
 * Definition for a binary tree node.
 * 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 inorderTraversalHelper(TreeNode* root, vector<int>& result) {
        if(!root) return;
        inorderTraversalHelper(root->left, result); //遍历左子树
        result.push_back(root->val); //访问中根节点
        inorderTraversalHelper(root->right, result); //遍历右子树 
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        inorderTraversalHelper(root, result);
        return result;
    }
};

关于二叉树的定义

这个部分定义的是二叉树节点 TreeNode 的构造函数（constructor）。在 C++ 中，构造函数用于初始化类的对象，即在创建对象时给它的成员变量赋初值。

详细解释：

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) {}
};

1. `TreeNode() : val(0), left(nullptr), right(nullptr) {}`

这是无参构造函数，即创建节点时如果没有提供初始值，将使用默认值初始化成员变量：

val(0)：将节点的值 val 初始化为 0。
left(nullptr)：将左子节点指针 left 初始化为 nullptr，表示该节点暂时没有左子节点。
right(nullptr)：将右子节点指针 right 初始化为 nullptr，表示该节点暂时没有右子节点。

2. `TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}`

这是带一个参数的构造函数，在创建节点时可以提供一个整数 x 作为节点的值 val。其余成员变量的初始化：

val(x)：将节点的值 val 初始化为 x，即创建节点时用 x 作为它的值。
left(nullptr)：左子节点指针 left 被初始化为 nullptr，表示没有左子节点。
right(nullptr)：右子节点指针 right 被初始化为 nullptr，表示没有右子节点。

3. `TreeNode(int x, TreeNode left, TreeNode right) : val(x), left(left), right(right) {}`

这是带三个参数的构造函数，可以在创建节点时同时指定节点的值 val 和它的左右子节点：

val(x)：将节点的值 val 初始化为 x。
left(left)：将左子节点指针 left 初始化为传入的 left 指针，这个指针指向另一个 TreeNode 节点。
right(right)：将右子节点指针 right 初始化为传入的 right 指针，同样指向另一个 TreeNode 节点。

总结：

第一个构造函数是无参的，它默认创建一个值为 0 的节点，没有子节点。
第二个构造函数允许创建一个带有值的节点，但没有子节点。
第三个构造函数允许创建一个带有值的节点，并且可以指定其左右子节点。

使用示例：

无参构造函数：

TreeNode node;  // 创建一个值为0的节点，左右子节点都是nullptr

带一个参数的构造函数：

TreeNode node(5);  // 创建一个值为5的节点，左右子节点都是nullptr

带三个参数的构造函数：

TreeNode leftNode(2);  // 创建左子节点，值为2
TreeNode rightNode(3);  // 创建右子节点，值为3
TreeNode root(1, &leftNode, &rightNode);  // 创建根节点，值为1，左子节点是leftNode，右子节点是rightNode