您的位置:首页 > 教育 > 锐评 > Leetcode 二叉树中根遍历

Leetcode 二叉树中根遍历

2024/11/4 1:31:51 来源:https://blog.csdn.net/coldasice342/article/details/142204052  浏览:    关键词:Leetcode 二叉树中根遍历

在这里插入图片描述

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

算法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 的节点,没有子节点。
  • 第二个构造函数允许创建一个带有值的节点,但没有子节点。
  • 第三个构造函数允许创建一个带有值的节点,并且可以指定其左右子节点。

使用示例:

  1. 无参构造函数:
TreeNode node;  // 创建一个值为0的节点,左右子节点都是nullptr
  1. 带一个参数的构造函数:
TreeNode node(5);  // 创建一个值为5的节点,左右子节点都是nullptr
  1. 带三个参数的构造函数:
TreeNode leftNode(2);  // 创建左子节点,值为2
TreeNode rightNode(3);  // 创建右子节点,值为3
TreeNode root(1, &leftNode, &rightNode);  // 创建根节点,值为1,左子节点是leftNode,右子节点是rightNode

在第三个例子中,root 是一个二叉树的根节点,它的左子节点是 leftNode,右子节点是 rightNode,构成了一个简单的二叉树。

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com