day014(二叉树章节)+北境互娱游戏开发一面

222.完全二叉树节点的个数

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

 思路:简单，层序遍历，每遍历一次，将队列中节点个数累加起来，最后返回即可。

class Solution {
public:
    int countNodes(TreeNode* root) {
            queue<TreeNode*> que;
            if(root!=nullptr){
                que.push(root);
            } 
            int NodeNum=0;
            while(!que.empty()){
                int size=que.size();
                NodeNum+=size;
                for(int i=0;i<size;i++){
                    TreeNode* node=que.front();
                    que.pop();
                    if(node->left)
                    que.push(node->left);
                    if(node->right)
                    que.push(node->right);
                }
            }
            return NodeNum;
    }
};

257.二叉树的所有路径节点

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

 1.思路:新创建一个函数travelRoot，用于实现递归.
首先递归三部曲1.确定传入参数 二叉树根节点，字符串path用于存储路径，字符串向量vector<string> 用于存储最终结果
2.确定终止条件
当 当前节点的左右节点都为空时 代表到达叶子节点 返回
3.确定单层递归逻辑
首先将根节点放入字符串向量中（要转成string类型），然后写终止条件（因为如果是最后一个节点 就不用加->了），之后再将path加上“->”进入递归。

class Solution {
public:
   void travelRoot(TreeNode* cur,vector<string>& res,string path){
    if(cur==nullptr){
        return ;
    }
       path+=to_string(cur->val);
        if(cur->left==nullptr&&cur->right==nullptr){
            res.push_back(path);
            return;
       }
         path+="->";
        travelRoot(cur->left,res,path);
        travelRoot(cur->right,res,path);
        return;
    }
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        string path;
        if(root==nullptr){
            return res;
        }
        travelRoot(root,res,path);
        return res;
    }
};

 404.左叶子之和

给定二叉树的根节点 root ，返回所有左叶子之和。

 思路:深度优先，根据左节点的性质--节点A左孩子不为空,节点A的左孩子的左右节点为空,那么此时,节点A的左孩子就是左节点，据此性质，通过递归找到左节点并进行相加操作，最后返回

class Solution {
public:
    void leftNode(TreeNode* root,int& result){
         if(root==nullptr){
            return ;
        }
        if(root->left!=nullptr&&root->left->left==nullptr&&root->left->right==nullptr){
            result+=root->left->val;
        }
        if(root->left==nullptr&&root->right==nullptr){
            return ;
        }
        leftNode(root->left,result);
        leftNode(root->right,result);
    }
    int sumOfLeftLeaves(TreeNode* root) {
    //节点A左孩子不为空,节点A的左孩子的左右节点为空,那么此时,节点A的左孩子就是左节点
    int result=0;
    leftNode(root,result);
        return result;
    }
};

513.找出树左下角的值

思路:用层序遍历,就很简单，只需要每次都记录第一个节点就可以了

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> que;
        int result=0;
        if(root==nullptr)
        return 0;
        que.push(root);
        while(!que.empty()){
            int size=que.size();
            for(int i=0;i<size;i++){
                TreeNode* node=que.front();
                que.pop();
                if(i==0)
                result=node->val;
                if(node->left)
                que.push(node->left);
                if(node->right)
                que.push(node->right);
            }
        }
          return result;
    }
  
};

游戏开发一面:问了半个小时左右

1.说说你对内存泄漏的理解?如何预防 内存分配是怎么样的

说了动态分配内存空间没有回收，野指针等，预防说了智能指针

2.智能指针

3.栈溢出怎么办?如何解决

4.四种强制类型转换

5.new和malloc的区别 底层

6.深拷贝浅拷贝

7.如何拷贝一段内存空间

8.C++如何判断是基类指针还是派生类指针
9.如何判断是属于父类还是属于子类（*)
10.TCP粘包是如何解决的 你的项目里是如何解决的(**)

我采用的是先收包大小，再收包内容。
11. TCP协议 重传机制 如何判断是否丢包
12.你的项目中极大极小搜索算法是如何实现的?

总结:有些想做游戏开发，但是我没有学Unity等知识基础，面试官也问了我有没有这方面基础，我说没有计算机图形学基础。。