层次遍历

C++ 代码 O(N)

/**
 * 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:
    // level traversal, if level k has x non-null nodes
    // level k+1 must have 2 * x nodes, no matter non-null nodes' children are null or not
    // if an encoded node is null, it's child wont be endoded
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string ans = "[";
        queue<TreeNode*> q;
        auto dummy = new TreeNode(1001);
        if(root) q.push(root);
        while(q.size()) {
            int size = q.size();
            bool has_child = false;
            for(int i = 0; i < size; i++) {
                auto p = q.front(); q.pop();
                if(p->val == 1001)  ans += "null,";
                else {
                    ans += to_string(p->val);
                    ans += ',';
                    if(p->left) q.push(p->left), has_child = true;
                    else q.push(dummy);
                    if(p->right) q.push(p->right), has_child = true;
                    else q.push(dummy);
                }
            }
            if(!has_child) break;
        }
        if(ans.back() == ',') ans.pop_back();
        ans += ']';
        delete dummy;
        return ans;
    }

    int read_int(string& data, int& idx) {
        int val = 0;
        bool neg = false;
        if(data[idx] == '-') neg = true, idx++;
        for(char ch = data[idx]; isdigit(ch); ch = data[++idx]) 
            val = val * 10 + (ch - '0');
        if(neg) val *= -1;
        return val;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data.size() == 2) return NULL;
        int idx = 1;
        TreeNode* ans = new TreeNode(read_int(data, idx));
        queue<TreeNode*> q;
        q.push(ans);
        while(q.size()) {
            int n = q.size();
            for(int i = 0; i < n; i++) {
                auto p = q.front(); q.pop();
                if(data[idx] == ',') idx++;
                if(data[idx] == 'n') idx += 4;
                else if(isdigit(data[idx]) || data[idx] == '-') 
                    p->left = new TreeNode(read_int(data, idx)), q.push(p->left);

                if(data[idx] == ',') idx++;
                if(data[idx] == 'n') idx += 4;
                else if(isdigit(data[idx]) || data[idx] == '-') 
                    p->right = new TreeNode(read_int(data, idx)), q.push(p->right);
            }
        }
        return ans;
    }
};