力扣 二叉树的锯齿形层序遍历-103

二叉树的锯齿形层序遍历-103

此题就是再二叉树层序遍历的基础上，加了反转当前层数组元素的函数reverse()，也可以不反转，直接在遍历当前层的所有节点的for循环里直接进行if判断，根据遍历方向，决定如何插入元素。

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {//二叉树的层序遍历
        vector<vector<int>> res;// 二维数组用来存储每层节点
        if(root == nullptr) return res;
        queue<TreeNode*> que;// 队列用来进行层序遍历
        que.push(root);// 将第一层的根节点加入队列中
        bool flag = true;//标记，用来标记每层的遍历方向
        while(!que.empty())
        {
            vector<int>vec;// 用于存储当前层的所有节点
            int n = que.size();// 当前层的节点个数
            for(int i=0;i<n;i++)//遍历当前层的所有节点
            {
                TreeNode* node = que.front();//将队列当前节点存下来
                que.pop();//将当前节点弹出队列
                //*************************************************************
                // 根据遍历方向，决定如何插入元素 
                // if (flag) {
                //     vec.push_back(node->val);  // 从左到右时，顺序插入
                // } else {
                //     vec.insert(vec.begin(), node->val);  // 从右到左时，将元素插入到开头
                // }
                //*************************************************************
                vec.push_back(node->val);//将存下来的当前节点
                if(node->left)que.push(node->left);//如果当前节点有左节点，加入队列
                if(node->right)que.push(node->right);//如果当前节点有右节点，加入队列
            }
            if(!flag)reverse(vec.begin(),vec.end());//翻转当前层数组中的元素
            res.push_back(vec);//将当前层的节点值加入结果
            flag = !flag;//反转遍历方向
        }
        return res;
    }
};

每日问题

什么是内存对齐？为什么需要内存对齐？

什么是内存对齐？

内存对齐（Memory Alignment） 是指计算机系统中数据存储的方式，要求数据按照特定的边界（通常是数据类型的大小）存储在内存中。也就是说，数据在内存中的地址应该是其大小的整数倍。

内存对齐的基本概念：

• 例如，32位的整数（int）通常需要存储在4字节边界上，也就是说，int 类型的变量地址应该是4的倍数。如果将一个32位整数存储在一个不是4的倍数的地址上，就会违反内存对齐规则。
• 相应地，64位的长整型（long long）通常需要存储在8字节边界上，因此它的地址应该是8的倍数。

内存对齐的规则通常依赖于机器架构和编译器。例如，在x86和ARM架构中，内存对齐是非常重要的，因为CPU对未对齐的访问可能会导致效率下降或者运行时错误。

为什么需要内存对齐？

内存对齐的主要原因有以下几点：

1.提高访问效率：

        在现代CPU中，数据通常通过总线进行传输。如果数据在内存中不按照特定的边界对齐，CPU可能需要进行额外的操作来访问数据，导致访问速度变慢。例如，某些CPU只能在字边界上高效访问数据。如果数据没有按照字边界对齐，CPU就必须进行多次内存读取，增加了访问的时间。

2.硬件限制：

        某些硬件平台（尤其是一些较旧的或嵌入式的处理器）要求内存对齐，否则会导致硬件错误。例如，一些处理器对于不对齐的访问会抛出异常或者产生未定义的行为。

3.内存访问的优化：

        现代处理器通常有内存缓存（cache），并且内存访问往往是按块进行的。数据对齐可以确保处理器能够一次性加载一个内存块，这样可以减少内存访问次数，从而提高性能。

4.节省内存：

        通过合理的内存对齐，编译器可以优化数据结构布局，尽量减少内存浪费。比如，在结构体（struct）中，编译器会通过插入填充字节（padding）来确保成员变量的对齐，从而使得每个变量能够尽可能高效地访问。

内存对齐的例子

假设我们有一个结构体 struct，包含多个不同大小的数据类型。我们来看一个简单的例子：

struct Example {
    char c;      // 1字节
    int i;       // 4字节
};

未对齐的布局：

在某些编译器中，char 类型的 c 会被存储在起始地址，紧接着 int 类型的 i 会被存储在接下来的内存位置，但由于 int 通常需要 4 字节对齐，编译器会插入一些填充字节（padding）来使 i 的地址是 4 的倍数。这种布局可能是这样的：

| char (1 byte) | padding (3 bytes) | int (4 bytes) |

总共需要 8 字节来存储这个结构体。

对齐后的布局：

为了确保内存对齐，int 类型的数据必须按照 4 字节边界存储。编译器会在 char 和 int 之间插入填充字节，使得 int 从 4 字节的地址开始：

| char (1 byte) | padding (3 bytes) | int (4 bytes) |

结果是，整个结构体占用 8 字节，其中 3 个字节是为了对齐 int 而插入的填充字节。

内存对齐的影响

1.性能：

        对齐能够提高程序的内存访问效率，减少由于跨越多个内存区域（非对齐数据）导致的访问开销。

2.内存浪费：

        为了保证内存对齐，结构体或数组中可能会插入一些填充字节。这些填充字节虽然没有被实际使用，但会导致内存浪费。例如，在一个包含多个不同类型字段的结构体中，可能会出现一些无用的内存占用。

内存对齐的处理

不同的编译器和平台可能对内存对齐的要求有所不同，但大多数现代编译器都会自动处理内存对齐问题。你也可以通过编译器提供的相关指令来控制内存对齐。例如，使用 #pragma pack 或 __attribute__((packed)) 等指令来改变结构体的对齐方式。

示例：在GCC中使用 __attribute__((packed))

struct __attribute__((packed)) Example {
    char c;
    int i;
};

使用 __attribute__((packed)) 可以告诉编译器不要插入填充字节，这样可以减少内存的占用，但会牺牲性能（因为这可能会导致不对齐的访问）。

总结

• 内存对齐是指将数据存储在内存中的地址遵循一定的对齐规则，使得数据存储在内存的边界上，这通常是数据类型大小的整数倍。
• 为什么需要内存对齐：内存对齐提高了数据访问的效率，避免了硬件故障，并确保数据访问的性能。
• 内存对齐的影响：虽然内存对齐可以提高性能，但有时可能会浪费内存，特别是在结构体中需要插入填充字节时。

通过合理利用内存对齐，可以有效提升程序的执行效率并减少内存访问的时间开销。