英雄游戏面经---冷不丁的挂了

十月份的KPI面，我也是无语，真的全部都答上了，面试官问问题的时候总停顿十几秒场面上真的尴尬。
不过没有游戏经验，就这样吧。

一、笔试题：

二叉树权值

有一棵二叉树，树上每个点标有权值，权值各不相同，请设计一个算法算出权值最大的叶节点到权值最小的叶节点的距离。二叉树每条边的距离为1，一个节点经过多少条边到达另一个节点为这两个节点之间的距离。给定二叉树的根节点root，请返回所求距离。我看大佬用的map算二进制编码，然后计算距离。大佬们太秀了，好好学学

struct TreeNode{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};

void GetCode(map<int,string>& treeMap,TreeNode* root,string s)
{
    if(root->left==nullptr && root->right==nullptr){
        //给出01编码
        treeMap[root->val] = s;
        return;
    }
    if(root->left!=nullptr){
        GetCode(treeMap,root->left,s+'0');
    }
    if(root->right!=nullptr){
        GetCode(treeMap,root->right,s+'1');
    }
}


int getDis(TreeNode* root)
{
    if(root == nullptr)
        return 0;

    map<int,string> treeMap;

    GetCode(treeMap,root,"");
 //利用迭代器获取开头结尾的值（map会自动排序）
    auto minNum = treeMap.begin();
    string s1 = minNum->second;
    auto maxNum = (--treeMap.end());
    string s2 = maxNum->second;

 //根据编码计算距离
    int i = 0,j = 0;
    while(i<s1.size() && j<s2.size() && s1[i] == s2[j]){
        i++;j++;
    }
    return s1.size() + s2.size() - i - j;
}

分割链表

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode* small = new ListNode(0);
        ListNode* smallHead = small;
        ListNode* large = new ListNode(0);
        ListNode* largeHead = large;
        while (head != nullptr) {
            if (head->val < x) {
                small->next = head;
                small = small->next;
            } else {
                large->next = head;
                large = large->next;
            }
            head = head->next;
        }
        large->next = nullptr;
        small->next = largeHead->next;
        return smallHead->next;
    }
};

最大正方形

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if(matrix.size() == 0 || matrix[0].size() == 0) return 0;
        int rows = matrix.size();
        int cols = matrix[0].size();
        vector<vector<int>> dp(rows, vector<int>(cols,0));
        int maxSize = 0;
        for(int i = 0; i < rows; ++i){
            for(int j = 0; j < cols; ++j){
                if(matrix[i][j] == '1'){
                    if(i == 0 || j == 0){
                        dp[i][j] = 1;
                    }else{
                        dp[i][j] = min(dp[i-1][j],min(dp[i-1][j-1], dp[i][j-1])) + 1;
                    }
                    maxSize = max(dp[i][j], maxSize);
                }
            }
        }
        return maxSize*maxSize;
    }
};