一面代码题

*****************

/**
 * 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 {
    void dfs(TreeNode *cur, vector<vector<int>>& result, int level) {
        if (cur == nullptr) {
            return;
        }

        if (level >= result.size()) {
            result.push_back(vector<int>());
        }
        if (level % 2 == 0) {
            result[level].push_back(cur->val);
        } else {
            result[level].insert(result[level].begin(), cur->val);
        }

        dfs(cur->left, result, level + 1);
        dfs(cur->right, result, level + 1);
        return;
    }

    void bfs(TreeNode *root, vector<vector<int>>& result) {
        if (root == nullptr) {
            return;
        }

        queue<TreeNode *> q;
        int level = 0;
        q.push(root);
        while (!q.empty()) {
            if (level >= result.size()) {
                result.push_back(vector<int>());
            }
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                TreeNode *cur = q.front();
                q.pop();
                if (level % 2 == 0) {
                    result[level].push_back(cur->val);
                } else {
                    result[level].insert(result[level].begin(), cur->val);
                }

                if (cur->left) { q.push(cur->left); }
                if (cur->right) { q.push(cur->right); }
            }
            level++;
        }
    }

public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> result;
        // dfs(root, result, 0);
        bfs(root, result);
        return result;
    }
};

二面代码题

*************

class Solution {
    unordered_map<Node *, Node *> memo;
public:
    Node* copyRandomList(Node* head) {
        if (head == nullptr) {
            return nullptr;
        }

        if (memo.count(head)) {
            return memo[head];
        }

        Node *cur = new Node(head->val);
        memo[head] = cur;

        cur->next = copyRandomList(head->next);
        cur->random = copyRandomList(head->random);
        return cur;
    }
};

追问有没有不占用O(N)空间的方法，没想出来。

下面是题解的不需要额外O(N)空间的代码。

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == nullptr) {
            return nullptr;
        }
        for (Node* node = head; node != nullptr; node = node->next->next) {
            Node* nodeNew = new Node(node->val);
            nodeNew->next = node->next;
            node->next = nodeNew;
        }
        for (Node* node = head; node != nullptr; node = node->next->next) {
            Node* nodeNew = node->next;
            nodeNew->random = (node->random != nullptr) ? node->random->next : nullptr;
        }
        Node* headNew = head->next;
        for (Node* node = head; node != nullptr; node = node->next) {
            Node* nodeNew = node->next;
            node->next = node->next->next;
            nodeNew->next = (nodeNew->next != nullptr) ? nodeNew->next->next : nullptr;
        }
        return headNew;
    }
};

作者：力扣官方题解
链接：***************************************************************************************************************************
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

技术面的八股就是很常规的C++八股，二面聊了聊实习，三面纯闲聊。