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

  • 0

    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 {
        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();
                TreeNode* node = curr.first;
                int idx = curr.second + lc;
                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.