4ms C++ solution DFS get tree span + BFS assign column index


  • 0
    C

    Sharing my solution which runs in 4ms.

    DFS to get the left-right span of the tree, so we can avoid reconstructing the final results and we can map our column index directly into final result vector index by final_index = column_index + left_node_span.

    BFS to assign column index to each node and add value directly into the result vector.

    class Solution {
    public:
        typedef pair<TreeNode*, int> Node;
        vector<vector<int>> verticalOrder(TreeNode* root) {
            if (root == NULL) return {};
            
            int lc = 0, rc = 0;
            getSpan(root, 0, lc, rc);
            lc = abs(lc);
            int count = lc + rc + 1;
            
            vector<vector<int>> vertical(count);
            
            queue<Node> next;
            next.push(Node(root, 0));
            
            while (!next.empty()) {
                Node curr = next.front();
                next.pop();
                
                TreeNode* node = curr.first;
                int idx = curr.second + lc;
                vertical[idx].push_back(curr.first->val);
                
                if (node->left) next.push(Node(node->left, curr.second-1));
                if (node->right) next.push(Node(node->right, curr.second+1));
            }
            
            return vertical;
        }
        
        void getSpan(TreeNode* curr, int coord, int& lc, int& rc) {
            if (coord < 0) lc = min(lc, coord);
            if (coord > 0) rc = max(rc, coord);
            if (curr->left) getSpan(curr->left, coord-1, lc, rc);
            if (curr->right) getSpan(curr->right, coord+1, lc, rc);
        }
    };
    

Log in to reply
 

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