Description
Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
Solution
We will need to get a right most node in each layer of tree. To do so, we will do a DFS and search right children first. If the right most node does not exist for this layer yet, add it to the output.
Implementation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void runner(int depth, TreeNode* root, vector<int>& output) {
if (!root) return;
if (output.size() == depth) output.push_back(root->val);
runner(depth+1, root->right, output);
runner(depth+1, root->left, output);
}
vector<int> rightSideView(TreeNode* root) {
vector<int> output;
runner(0, root, output);
return output;
}
};