Clean c++ BFS solution


  • 0
    vector<vector<int>> verticalOrder(TreeNode* root) {
        vector<vector<int>> results;
        if (root == NULL)
            return results;
        map<int, vector<int>> records;
        queue<pair<TreeNode *, int>> nodes;
        nodes.push(make_pair(root, 0));
        while (nodes.size()) {
            TreeNode *root = nodes.front().first;
            int current = nodes.front().second;
            nodes.pop();
            records[current].push_back(root->val);
            if (root->left) {
                nodes.push(make_pair(root->left, current - 1));
            }
            if (root->right) {
                nodes.push(make_pair(root->right, current + 1));
            }
        }
        for (auto record : records) {
            results.push_back(record.second);
        }
        return results;
    }
    

  • 2

    I had exactly same solution as yours! However, since std::mapis ordered STL container, every query operator [] runs O(log N)time, so the overall time complexity will be O(N*logN), where Nis the number of nodes in the tree.
    As some optimized solutions posted by others, an improvement can be made by using std::unordered_mapto store index to node values. The trick is that, eventually, the indices must continuously cover a range. So just keep tracking the max and min indices while writing records. Finally, a traversal from min index to max index in std::unordered_map will return the desired result. The improved time complexity is O(N).


  • 0

    @zzg_zzm Sounds great! Upvote


Log in to reply
 

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