C++ 1round BFS


  • 0
    I
    class Solution {
    public:
        vector<vector<string>> printTree(TreeNode* root) {
            queue<pair<TreeNode*, vector<int>>> q;
            queue<pair<TreeNode*, vector<int>>> m;
            TreeNode* guard = NULL;
            vector<int> s = {1};
            q.push(make_pair(root, s));
            int l = 0;
            while (!q.empty()) {
                q.push(make_pair(guard, s));
                l++;
                while (q.front().first!=guard) {
                    auto p = q.front();
                    if (p.first->left) {
                        vector<int> ls = p.second;
                        ls.push_back(-1);
                        q.push(make_pair(p.first->left, ls));
                    }
                    if (p.first->right) {
                        vector<int> rs = p.second;
                        rs.push_back(1);
                        q.push(make_pair(p.first->right, rs));
                    }
                    m.push(p);
                    q.pop();
                }
                m.push(q.front());
                q.pop();
            }
            vector<vector<string>> res;
            while (!m.empty()) {
                vector<string> r(pow(2, l)-1, "");
                while (m.front().first!=guard) {
                    auto p = m.front();
                    int pos = 0;
                    for (int i=0; i<p.second.size(); i++) {
                        pos += pow(2, l-1-i)*p.second[i];
                    }
                    r[pos-1] = to_string(p.first->val);
                    m.pop();
                }
                res.push_back(r);
                m.pop();
            }
            return res;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.