小米C++笔试分享

1、堆和栈的区别

2、虚函数的原理、多态的底层实现

3、如果一个类里面只有虚函数的话，大小为多少（4或8个字节）

4、解释一下c++智能指针

5、c++内存对齐

6、代码先手写的一个层序遍历 ， 自己定义二叉树 输出结果

7、层序遍历升级：类似下面这个题，实现出来

解题思路：将树的每一层节点用next指针串起来，这样每一层会形成一个单链表，思路很简单，在层序遍历上加一点东西即可

附上我的代码

#include

#include "queue"

#include "vector"

using namespace std;

struct TreeNode

{

int val;

TreeNode* left;

TreeNode* right;

TreeNode* next;

TreeNode(int value):val(value),left(nullptr),right(nullptr),next(nullptr)

{

}

};

vector level;

vector operateTree(TreeNode* root)

{

if(!root) return level;

queue q;

q.push(root);

while(!q.empty())

{

int size=q.size();

for(int i=0;i

{

TreeNode *t=q.front();

q.pop();

if(i!=size-1)

t->next = q.front();

level.push_back(t);

if(t->left)

{

q.push(t->left);

}

if(t->right)

{

q.push(t->right);

}

}

}

return level;

}

int main() {

TreeNode *root=new TreeNode(0);

root->left=new TreeNode(1);

root->right=new TreeNode(2);

root->left->left=new TreeNode(3);

root->left->right=new TreeNode(4);

root->right->left=new TreeNode(5);

root->right->right=new TreeNode(6);

operateTree(root);

for(auto node:level)

{

if(node->next==nullptr)

{

cout<<"cur node: "<val<<"->"<<"nullptr"<

}

else

{

cout<<"cur node: "<val<<"->"<next->val<

}

}

}