二叉树(使用C++实现)

😲示例

二叉树在C++中的一般写法如下所示, 其中nullptr和NULL都是在C++中被承认的空指针表示方法

1
2
3
4
5
6
7
8
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) {}
};

🤔一些疑问解答

nullptr和NULL有什么区别?

NULL和nullptr都用于表示空指针，但它们有一些区别。

NULL是一个宏定义，通常被定义为整数0。在早期的C++标准中，NULL被用作空指针的表示。然而，由于整数0也可以被用于表示其他含义，例如整数类型的零值，这可能导致一些潜在的问题。因此，在C++11标准中，引入了新的关键字nullptr来表示空指针。

nullptr是一个关键字，专门用于表示空指针。与NULL不同，nullptr的类型是nullptr_t，它是一个独立的类型，可以隐式转换[1]为任何指针类型。这样可以避免了NULL可能引起的一些类型转换问题。

使用nullptr可以提供更好的类型安全性，因为它只能用于指针类型，而不能用于整数类型。这样可以在编译时捕获一些潜在的错误。

总结一下，NULL是一个宏定义，通常被定义为整数0，而nullptr是一个关键字，用于表示空指针，并提供了更好的类型安全性。在现代的C++代码中，推荐使用nullptr来表示空指针。

💪力扣刷题

144. 二叉树的前序遍历

力扣传送门

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * 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:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        dfs(root,result);
        return result;
    }
    void dfs(TreeNode* root, vector<int>& result){
        if(root==nullptr)
            return;
        result.push_back(root->val);
        dfs(root->left,result);
        dfs(root->right,result);
    }
};

145. 二叉树的后序遍历

力扣传送门

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        dfs(root,result);
        return result;
    }
    void dfs(TreeNode* root, vector<int>& result){
        if(root==nullptr)
            return;
        dfs(root->left,result);
        dfs(root->right,result);
        result.push_back(root->val);
    }
};

94. 二叉树的中序遍历

力扣传送门

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        dfs(root,result);
        return result;
    }
    void dfs(TreeNode* root, vector<int>& result){
        if(root==nullptr)
            return;
        dfs(root->left,result);
        result.push_back(root->val);
        dfs(root->right,result);
    }
};
  1. 例如byte类型的数字12可以隐式转换为int类型,但是int类型的12转换为byte类型需要显式转换,(byte)12,这里展示的是在高级语言中显隐式转换如何体现,高精度和低精度的转换关系,然而它在编译中一定有另一种体现方式,这里的nullptr_t类型可以隐式转换为任何类型便是这个意思,它可以在汇编层面隐式转换为任何类型,而不是我们常规理解的在高级语言层面的高低精度转换

    ↩

技术笔记
#算法 #数据结构 #C++ #力扣刷题 #Java转C++
二叉树(使用C++实现)
http://example.com/二叉树/
作者
李小基
许可协议