C++ level order traverse with queue


  • 0
    H

    Because it requires top to bottom in order, we can't user in-order recursively find out the most left column i.e. res[0]. So we have to do level order traverse. The key point is with more left nodes coming in, the column index will keep shifting to right.
    If array allow negative index, it won't be a problem. But negative index is not allowed. How to achieve that? The idea is to use offset to map a negative index based array to a zero index based array.

        vector<vector<int>> verticalOrder(TreeNode* root) {
            vector<vector<int>> res;
            if (!root) return res;
            queue<pair<TreeNode*, int>> q;
            q.push(make_pair(root, 0));
            int offset = 0;
            while (!q.empty()) {
                pair<TreeNode*, int> p = q.front();
                TreeNode* node = p.first;
                int col = p.second;
                q.pop();
                int idx = col - offset;
                offset = min(offset, col);
                
                if (idx == res.size()) res.push_back(vector<int>(1, node->val));
                else if (idx < 0 ) res.insert(res.begin(), vector<int>(1, node->val));
                else res[idx].push_back(node->val);
                
                if (node->left) q.push(make_pair(node->left, col-1));
                if (node->right) q.push(make_pair(node->right, col+1));
            }
            return res;
        }
    

Log in to reply
 

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