Jan 29 - Daily Programming Diary

29.01.2021 — Diary, Programming — 1 min read

17:00

In Gurgaon now! Let's just quickly solve today's Leetcode challenge.

This seems to be more of a implementation problem that the concept. I'll make a map that maps x coordinate to the "map that maps the y coordinate to the node value".

vertical-order-traversal-of-a-binary-tree

1map<int, map<int, set<int>>> m;
2
3void traverse(TreeNode *root, int x, int y) {
4    if (root == NULL) {
5        return;
6    }
7
8    m[x][y].insert(root->val);
9
10    traverse(root->left, x - 1, y + 1);
11    traverse(root->right, x + 1, y + 1);
12}
13
14vector<vector<int>> verticalTraversal(TreeNode *root) {
15    traverse(root, 0, 0);
16
17    vector<vector<int>> v;
18
19    for (auto a : m) {
20        vector<int> wow;
21        for (auto b : a.second) {
22            set<int> temp = b.second;
23            wow.insert(wow.end(), temp.begin(), temp.end());
24        }
25        v.push_back(wow);
26    }
27
28    return v;
29}

The time complexity is O(N) where N is the number of nodes, and space complexity is also O(N)

Samsung test tomorrow, all the best Paras!

EOD Checklist

Leetcode January Challenge
This blog