Feb 6 - Daily Programming Diary

14:00

Let's start today's Leetcode challenge. It looks a bit weird, the question doesn't seem to provide appropriate information.

My approach is to traverse the right path and printing it in order. Now this approach seems to be wrong and I can understand why. "Standing on the right" of the tree means seeing the tree from the right and seeing the first node that's in front. So I need to traverse the tree using preorder traversal and store the node values on left tree with their heights, and if a node exists to it's right on the same level, update the value.

Copybinary-tree-right-side-view.cpp: copy code to clipboard
1map<int, int> m;
2
3void traverse(TreeNode *root, int height) {
4    if (!root) return;
5
6    m[height] = root->val;
7    traverse(root->left, height + 1);
8    traverse(root->right, height + 1);
9}
10
11vector<int> rightSideView(TreeNode *root) {
12    traverse(root, 0);
13
14    vector<int> v;
15
16    for (auto a : m) {
17        v.push_back(a.second);
18    }
19
20    return v;
21}

The complexity is O(N) and space complexity is O(N) where N is the number of nodes in the tree.

Bye!

EOD Checklist

• Leetcode February Challenge
• This blog