BFS + map


  • 0
    N

    Time complexity: O(N)
    Space Complexity: O(N)

    class Solution {
    public:
        vector<vector<int>> verticalOrder(TreeNode* root) {
            vector<vector<int>> res;
            if (root == NULL)
                return res;
            queue<pair<int, TreeNode*>> q;
            map<int, vector<int>> table;
            TreeNode* tmp_node = NULL;
            int tmp_col = 0;
            q.push(make_pair(0, root));
            while(!q.empty()) {
                tmp_node = q.front().second;
                tmp_col = q.front().first;
                q.pop();
                table[tmp_col].push_back(tmp_node->val);
                if (tmp_node->left) {
                    q.push(make_pair(tmp_col - 1, tmp_node->left));
                }
                
                if (tmp_node->right) {
                    q.push(make_pair(tmp_col + 1, tmp_node->right));
                }
            }
            
            for(auto& ele : table) {
                res.push_back(ele.second);
            }
            
            return res;   
        }
    };
    
    
    1. Decide what nodes could be in same column ?
    2. I forgot map container which has sorted property by itself

Log in to reply
 

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