全bfs

序列化-> 正常bfs, queue空了结束，记得补上null
反序列化 -> bfs， queue + vector配合达到，遇到空子树跳过的效果（queue中弹出根节点，再用坐标idx定位其左右孩子）
vector->找孩子
queue->找根的(存left, right待赋值的节点)

1) 全部节点进入数组，因此可以更具坐标索引
2) 根节点入队，设此时idx坐标为0(根节点坐标)，idx+1就是左子，idx+2就是右子
3) 如果左或右不是空指针，加入queue（我们拿出左右孩子给根节点的left和right赋值，左右孩子本身也要加入queue中，等待给他们的left和right赋值）
4) 一次用掉两个idx，所以每次更新要+=2, 空指针情况咋办？👴这queue空指针这种臭弟弟也配进来？（所以还有一个if(!vNode[0])的判断),保证根节点也不是空的
5) 当queue空了，就收工了

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/


class Solution {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (!root) return "[null]";
        string res {'[' + to_string(root->val) + ','};

        deque<TreeNode*> dq {{root}};

        while(!dq.empty()) {
            auto node = dq.front(); dq.pop_front();

            if (node->left) {
                dq.push_back(node->left);
                res += to_string(node->left->val) + ',';
            } else res += "null,";


            if (node->right) {
                dq.push_back(node->right);
                res += to_string(node->right->val) + ',';
            } else res += "null,";

        }
        res[res.size()-1] = ']';
        return res;
    }


    // Decodes your encoded data to tree.
    TreeNode* deserialize(const string& data) {
        vector<TreeNode*> vNode {};

        istringstream iss {data.substr(1, data.size()-2)};
        string token {};

        while (getline(iss, token, ',')) {
            if (token =="null") 
                vNode.emplace_back(nullptr);
            else 
                vNode.emplace_back(new TreeNode(stoi(token)));
        }

        // root is valid!
        if (!vNode[0]) return nullptr;

        // root
        queue<TreeNode*> qNode {{vNode[0]}};

        int idx = 0;
        while (!qNode.empty()) {
            auto root = qNode.front(); qNode.pop();
            root->left = vNode[idx+1];
            root->right = vNode[idx+2];
            if (root->left) qNode.push(root->left);
            if (root->right) qNode.push(root->right);
            idx+=2;
        }

        return vNode[0];
    }

};

dfs太费脑不适合我这种弱智