My Solution in C++


  • 13
    R

    class Solution {
    public:

    vector<vector<int>> verticalOrder(TreeNode* root) {
        vector<vector<int>> output;
        if(!root){
            return output;
        }
        map<int, vector<int>> m;
        queue<pair<int, TreeNode*>> q;
        q.push(make_pair(0,root));
        while(!q.empty()){
            int size = q.size();
            for(int i = 0;  i < size; i++){
                TreeNode* t = q.front().second;
                int tmp = q.front().first;
                q.pop();
                m[tmp].push_back(t->val);
                if(t->left){
                    q.push(make_pair(tmp - 1, t->left));
                }
                if(t->right){
                    q.push(make_pair(tmp + 1, t->right));
                    
                }
            }
        }
        for(auto& v : m){
            output.push_back(v.second);
        }
        return output;
        
    }
    

    };


  • 5

    Similar, but different in details:

    vector<vector<int>> verticalOrder(TreeNode* root) {
        map<int, vector<int>> cols;
        queue<pair<TreeNode*, int>> q;
        if (root)
            q.emplace(root, 0);
        while (q.size()) {
            auto node = q.front().first;
            int x = q.front().second;
            q.pop();
            cols[x].push_back(node->val);
            if (node->left)
                q.emplace(node->left, x-1);
            if (node->right)
                q.emplace(node->right, x+1);
        }
        vector<vector<int>> result;
        for (auto col : cols)
            result.push_back(col.second);
        return result;
    }
    

  • 1
    X

    Here is the java implementation

    public List<List<Integer>> verticalOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<List<Integer>>();
        }
        Map<Integer, List<Integer>> m = new TreeMap<>();
        Queue<TreeNode> queue = new LinkedList<>();
        Queue<Integer> verticalQueue = new LinkedList<>();
        queue.add(root);
        verticalQueue.add(0);
        while (queue.size() > 0) {
            for (int i = 0, size = queue.size(); i < size; i++) {
                TreeNode p = queue.poll();
                int idx = verticalQueue.poll();
                List<Integer> val = m.get(idx);
    
                if (val == null) {
                    val = new ArrayList<Integer>();
                    m.put(idx, val);
                }
                val.add(p.val);
    
                if (p.left != null) {
                    queue.offer(p.left);
                    verticalQueue.offer(idx - 1);
                }
    
                if (p.right != null) {
                    queue.offer(p.right);
                    verticalQueue.offer(idx + 1);
                }
            }
        }
    
        return new ArrayList<List<Integer>>(m.values());
    }

  • 2

    I think using unordered map and then search for a minimum key would be faster (at least in O representation).
    The reason is that hashtable gives very nice O(1) operations, while ordered_map gives O(logn) for insertion. This gives hashtable an overall of O(n) time complexity for overall performance (including searching for min key), while map has O(nlogn).


  • 2
    R

    @siriux Big O is not the best way to measure stuff. As unordered_map would give you O(N) when there is not enough memory. It is way more cost in memory compare with map. I understand it is faster when you have sufficient memory, but map has a really good performance when the tree is not big.
    so the key here is not using map or unordered_map, it is get the idea right and have an understanding of ups and downs in each datastructures. If you get that, you passed this problem.


Log in to reply
 

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