今天的題單：

• Binary Tree Level Order Traversal

• Clone Graph

102. Binary Tree Level Order Traversal

思路: 建一個 2D array，用 preorder traversal 紀錄樹的深度 (depth)，用樹的深度當作 index，把 node 按照順序放入 array。

Attempt 1: DFS

/**
 * 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 {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> levels;

        if (root == nullptr) return levels;
        
        preorder(root, 0, levels);
        return levels;
    }

    void preorder(TreeNode* node, int depth, vector<vector<int>>& levels){
        if (node == nullptr) return;
        if (levels.size() < depth + 1) {
            vector<int> new_level = {node->val};
            levels.push_back(new_level);
        } else {
            levels[depth].push_back(node->val);
        }
        preorder(node->left, depth + 1, levels);
        preorder(node->right, depth + 1, levels);
    }
};

Attempt 2: BFS

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> levels;

        queue<pair<TreeNode*, int>> q;

        q.push({root, 0});

        while (!q.empty()) {
            TreeNode* curr = q.front().first;
            int curr_depth = q.front().second;
            if (curr == nullptr) {
                q.pop();
            } else {
                if (levels.size() < curr_depth + 1) {
                    vector<int> new_level = {curr->val};
                    levels.push_back(new_level);
                } else {
                    levels[curr_depth].push_back(curr->val);
                }

                q.push({curr->left, curr_depth + 1});
                q.push({curr->right, curr_depth + 1});
                q.pop();
            }
        }

        return levels;
    }
    
};

133. Clone Graph

思路: 因為 node 的 value 是唯一的，可以建立一個 hashmap 紀錄 value 和新建的 node 的對應。接著用 DFS 走訪每一個 node: 如果 node 還沒被 clone 過就新建一個，登錄到 hashmap，然後再複製 neighbor。在複製 neighbor 前就會先建好 node 並登錄，避免一直遞迴的問題。

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }
    Node(int _val) {
        val = _val;
        neighbors = vector<Node*>();
    }
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/

class Solution {
public:
    Node* cloneGraph(Node* node) {
        map<int, Node*> hashmap;

        if (node == nullptr) {
            return nullptr; 
        }
        
        return clone_dfs(node, hashmap);
    }

    Node* clone_dfs(Node* ori_node, map<int, Node*>& hashmap) {
        // if created, then return
        if (hashmap.find(ori_node->val) != hashmap.end()) 
            return hashmap[ori_node->val];

        // create new node
        Node* clone_node = new Node(ori_node->val);

        // register new node
        hashmap[ori_node->val] = clone_node;

        // clone the neighbors
        for (int i = 0; i < ori_node->neighbors.size(); i++) {
            Node* new_node = clone_dfs(ori_node->neighbors[i], hashmap);
            clone_node->neighbors.push_back(new_node);
        }

        return clone_node;
    }
};