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

力扣对称二叉树-101

article 2025/1/21 3:04:21

对称二叉树-101

/**
 * 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:
    bool isSymmetric(TreeNode* root) {
        if(root == nullptr)return true;
        return cmp(root->left,root->right);
    }
    bool cmp(TreeNode* left1,TreeNode* left2)
    {
        //如果两个树都为空，返回true，表示对称。
        if(!left1&&!left2)return true;
        //如果上一个if没有执行没有返回true，并且这行if判断成立的话，就是一个树为空一个树不为空，返回false，表示不对称。
        if(!left1||!left2)return false;
        bool LandR = cmp(left1->left,left2->right);//递归左子树的左子节点与右子树的右子节点。
        bool RandL = cmp(left1->right,left2->left);//递归左子树的右子节点与右子树的左子节点。
        //如果每个节点对应的值相同，并且树的结构是对称的就返回true，否则返回false
        return left1->val==left2->val&&LandR&&RandL;
    }
};

每日问题

请解释new和malloc的区别，并分别解释他们的用法

new 和 malloc 都是用于动态内存分配的操作符，但它们在 C++ 和 C 语言中有所不同。以下是它们之间的区别以及各自的用法。

1. malloc（C语言）

malloc 是 C 语言中的函数，用于从堆（heap）中动态分配一块指定大小的内存。它的原型定义在头文件中。

语法：

void* malloc(size_t size);

size 是要分配的内存的字节数。

返回值是一个 void* 指针，指向分配的内存区域。如果分配失败，返回 NULL。

用法：

#include <stdlib.h>

int* ptr = (int*)malloc(sizeof(int) * 10);  // 分配10个int类型大小的内存
if (ptr == NULL) {
    // 内存分配失败，处理错误
}

特点：

malloc 只分配内存，不初始化内存。分配的内存中的值是未定义的。

需要手动进行类型转换（如 int*）。

分配失败时返回 NULL。

2. new（C++语言）

new 是 C++ 中的操作符，功能类似于 malloc，用于动态分配内存。new 会在堆上分配指定大小的内存，并且初始化对象（如果是类类型的话）。

语法：

pointer = new type;                 // 分配一个对象
pointer = new type[size];           // 分配一个数组

new 会返回指向分配内存区域的指针。如果分配失败，会抛出一个 std::bad_alloc 异常，而不是返回 NULL。

new[] 用于分配数组，new 用于分配单个对象。

用法：

#include <iostream>

int* ptr = new int(10);  // 分配一个int类型内存，并初始化为10
int* arr = new int[10];   // 分配10个int类型的数组

特点：

new 会初始化内存，如果是基础数据类型，则会将其初始化为默认值（例如，int 会初始化为 0）。对于类对象，会调用类的构造函数。

new 会自动进行类型转换。

如果内存分配失败，new 会抛出 std::bad_alloc 异常，而不是返回 NULL。

使用 new[] 分配的数组应该用 delete[] 来释放。

3. malloc 和 new 的区别

内存初始化：

malloc 不会初始化分配的内存，内存中的内容是未定义的。

new 会初始化内存，对于基本类型初始化为零，对于类类型会调用构造函数。

返回类型：

malloc 返回的是 void* 指针，需要手动进行类型转换。

new 返回的是指向指定类型的指针，自动进行类型转换。

异常处理：

malloc 如果分配失败，会返回 NULL，需要手动检查。

new 如果分配失败，会抛出 std::bad_alloc 异常。

适用语言：

malloc 是 C 语言中的函数，可以在 C 中使用。

new 是 C++ 中的操作符，推荐在 C++ 中使用。

4. 释放内存

使用 malloc 分配的内存必须使用 free 来释放：free(ptr);

使用 new 分配的内存必须使用 delete 来释放（单个对象）：delete ptr;

使用 new[] 分配的数组必须使用 delete[] 来释放：delete[] arr;

示例代码：

使用 malloc（C语言）：

#include <stdlib.h>
#include <stdio.h>

int main() {
    int* ptr = (int*)malloc(sizeof(int) * 5);  // 分配一个整数数组
    if (ptr == NULL) {
        printf("Memory allocation failed.\n");
        return 1;
    }

    // 使用内存
    for (int i = 0; i < 5; i++) {
        ptr[i] = i * 10;
        printf("%d ", ptr[i]);
    }

    // 释放内存
    free(ptr);
    return 0;
}

使用 new（C++语言）：

#include <iostream>
using namespace std;

int main() {
    int* ptr = new int(5);  // 分配一个整数并初始化为5
    cout << *ptr << endl;  // 输出5

    // 使用内存
    int* arr = new int[5];  // 分配一个数组
    for (int i = 0; i < 5; i++) {
        arr[i] = i * 10;
        cout << arr[i] << " ";
    }

    // 释放内存
    delete ptr;     // 释放单个对象
    delete[] arr;   // 释放数组
    return 0;
}

总结：

malloc 是 C 中的动态内存分配函数，返回 void* 类型的指针，不初始化内存。

new 是 C++ 中的操作符，返回指向指定类型的指针，并且会初始化内存，且支持异常处理。

malloc分配失败会导致什么问题

malloc 分配内存失败会导致一些潜在的问题，最主要的问题是程序没有获取到所需的内存空间。具体来说，malloc 分配内存失败时会返回 NULL，如果没有适当地处理这个错误，可能会导致以下几种情况：

1. 程序崩溃（Segmentation Fault）

如果 malloc 返回 NULL，而程序没有检查这一点，直接使用这个 NULL 指针进行读写操作，将导致程序崩溃，通常表现为 Segmentation Fault 或 Access Violation 错误。这是因为对空指针进行解引用是非法的。

示例：

#include <stdlib.h>

int main() {
    int* ptr = (int*)malloc(sizeof(int) * 1000000000);  // 请求分配过大的内存
    if (ptr == NULL) {
        // 忽略分配失败，直接使用指针
        *ptr = 10;  // 访问空指针，导致崩溃
    }
    return 0;
}

在这个示例中，malloc 分配失败时返回 NULL，但如果不检查 NULL，后续访问 *ptr 就会导致崩溃。

2. 未定义行为（Undefined Behavior）

如果 malloc 分配失败时没有检查其返回值并继续使用 NULL 指针，程序可能会出现未定义行为。未定义行为的后果是不可预测的，可能导致程序的正常功能丧失、数据损坏或其他逻辑错误。

示例：

#include <stdlib.h>

int main() {
    int* ptr = (int*)malloc(sizeof(int) * 1000);  // 请求内存
    // 忽略malloc失败的检查，继续使用ptr
    ptr[0] = 10;  // 如果malloc失败，ptr会是NULL，这里访问空指针，未定义行为
    return 0;
}

3. 内存泄漏

如果在 malloc 分配内存失败后没有正确处理（如没有及时释放之前分配的内存），可能会导致内存泄漏。内存泄漏指的是程序在结束时未释放已分配的内存，这会导致程序在运行时消耗更多的内存，最终可能导致系统内存不足或程序崩溃。

示例：

#include <stdlib.h>

int main() {
    int* ptr = (int*)malloc(sizeof(int) * 1000);  // 分配内存
    if (ptr == NULL) {
        // malloc失败，未释放之前已分配的内存
        // 忘记释放内存，造成内存泄漏
        return 1;
    }

    // 使用ptr
    free(ptr);  // 应该在使用后释放内存
    return 0;
}

4. 程序的逻辑错误

malloc 失败后，如果没有适当的错误处理，可能导致程序继续运行并且进入错误的执行路径，造成逻辑上的错误，甚至使程序产生错误的输出或行为。

示例：

#include <stdlib.h>
#include <stdio.h>

int main() {
    int* ptr = (int*)malloc(sizeof(int) * 1000);  // 分配内存
    if (ptr == NULL) {
        printf("Memory allocation failed!\n");
        return 1;  // 退出程序，避免继续执行
    }
    
    // 使用ptr
    printf("Memory allocated successfully.\n");
    free(ptr);  // 释放内存
    return 0;
}

5. 影响程序的性能或稳定性

如果 malloc 失败时没有及时处理或报告错误，可能会导致程序在长期运行中因内存不足而性能下降，甚至崩溃。在资源紧张的环境下，频繁的内存分配失败可能会逐步影响程序的稳定性。

解决办法：

1.检查返回值：

总是检查 malloc 返回的指针是否为 NULL，如果是，则说明内存分配失败。

int* ptr = (int*)malloc(sizeof(int) * 1000);
if (ptr == NULL) {
    // 处理内存分配失败的情况，如打印错误信息并退出程序
    printf("Memory allocation failed!\n");
    exit(1);
}

2.及时释放资源：

确保在程序退出之前，释放所有动态分配的内存，避免内存泄漏。

3.合理的内存请求：

避免请求过多的内存，尤其是在内存紧张的环境中，分配超大内存块时应该谨慎。

4.使用异常处理（在 C++ 中）：

如果你使用 C++，可以考虑使用 new 操作符，它在内存分配失败时会抛出 std::bad_alloc 异常，你可以使用异常处理机制来捕获这一异常。

使用 new（C++）示例：

#include <iostream>
#include <new>  // 用于std::bad_alloc

int main() {
    try {
        int* ptr = new int[1000000000];  // 尝试分配大量内存
        // 使用ptr
        delete[] ptr;  // 释放内存
    } catch (std::bad_alloc& e) {
        std::cout << "Memory allocation failed: " << e.what() << std::endl;
    }
    return 0;
}