6ms, c++, level order traverse with queue


  • 0
    class Solution {
    public:
    void levelTraverse(TreeNode* root, vector<vector<int>>& neg, vector<vector<int>>& pos){
        if (root==NULL) return;
        queue<pair<TreeNode*,int>> tree;
        TreeNode* cur;
        int level;
        tree.push(make_pair(root,0));
        while(!tree.empty()){
            cur = tree.front().first;
            level = tree.front().second;
            tree.pop();
            if (level>=0){
                if(level>=pos.size()){
                    vector<int> temp(1,cur->val);
                    pos.push_back(temp);
                }else{
                    pos[level].push_back(cur->val);
                }
            }else{
                int idx = -level-1;
                if (idx>=neg.size()){
                    vector<int> temp(1,cur->val);
                    neg.push_back(temp);
                }else{
                    neg[idx].push_back(cur->val);
                }
            }
            if (cur->left){
                tree.push(make_pair(cur->left,level-1));
            }
            if (cur->right){
                tree.push(make_pair(cur->right,level+1));
            }
        }
    }
    
    vector<vector<int>> verticalOrder(TreeNode* root) {
        vector<vector<int>> neg;
        vector<vector<int>> pos;
        levelTraverse(root,neg,pos);
        reverse(neg.begin(),neg.end());
        for(auto &x:pos){
            neg.push_back(x);
        }
        return neg;
    }
    };

Log in to reply
 

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