C++ 3ms solution without hashtable. beat 97%


  • 0
    M

    So i didn't use hash table as most solution did here, instead i find the total number of columns and do a level order traversal, then put each node at where they should be. It's O(2n) (hence O(n) time complexity) as most of solution here.

    class Solution {
    public:
        void loadColumn(TreeNode* root, int& leftColumn, int& rightColumn, int current) {
            if (root == NULL) {
                return;
            }
            else {
                leftColumn = min(leftColumn, current);
                rightColumn = max(rightColumn, current);
                if (root -> left) {
                    loadColumn(root -> left, leftColumn, rightColumn, current-1);
                }
                if (root -> right) {
                    loadColumn(root -> right, leftColumn, rightColumn, current+1);
                }
            }
        }
        vector<vector<int>> verticalOrder(TreeNode* root) {
            if (root == NULL) {
                return {};
            }
            int leftColumn = 0, rightColumn = 0;
            loadColumn(root, leftColumn, rightColumn, 0);
            int column = rightColumn - leftColumn + 1;
            
            vector<vector<int>> result(column);
            queue<pair<TreeNode*, int>> q;
            q.push(make_pair(root, -leftColumn));
            while(!q.empty()) {
                pair<TreeNode*, int> current = q.front();
                result[current.second].push_back(current.first->val);
                if (current.first -> left) {
                    q.push(make_pair(current.first->left, current.second-1));
                }
                if (current.first -> right) {
                    q.push(make_pair(current.first->right, current.second+1));
                }
                q.pop();
            }
            return result;
        }
    };
    

Log in to reply
 

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