forked from vaibhavpathak999/Algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathRightSideView.cpp
More file actions
89 lines (81 loc) · 2.2 KB
/
Copy pathRightSideView.cpp
File metadata and controls
89 lines (81 loc) · 2.2 KB
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <bits/stdc++.h>
using namespace std;
struct TreeNode
{
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
/* Logic in brief: Doing level order traversal, and then picking the rightmost at each level in answer */
const int N = 1e5 + 3;
class Solution
{
public:
vector<int> lvl[N];
int n;
void bfs(TreeNode *root)
{
queue<TreeNode *> q;
q.push(root);
n = 1;
lvl[1].push_back(root->val);
while (!q.empty())
{
TreeNode *curr;
n++;
int t = q.size();
for (int i = 0; i < t; i++)
{
curr = q.front();
q.pop();
if (curr->left != nullptr)
{
q.push(curr->left);
lvl[n].push_back(curr->left->val);
}
if (curr->right != nullptr)
{
q.push(curr->right);
lvl[n].push_back(curr->right->val);
}
}
}
}
vector<int> rightSideView(TreeNode *root)
{
vector<int> ans;
if (!root)
return ans;
bfs(root);
for (int i = 1; i <= n; i++)
{
if (lvl[i].size() > 0)
{
int x = lvl[i].size();
ans.push_back(lvl[i][x - 1]);
}
}
return ans;
}
};
int main()
{
TreeNode *root = new TreeNode(1);
TreeNode *node2 = new TreeNode(2);
TreeNode *node3 = new TreeNode(3);
TreeNode *node4 = new TreeNode(4);
TreeNode *node5 = new TreeNode(5);
root->left = node2;
root->right = node3;
node2->right = node5;
node3->right = node4;
Solution sol;
vector<int> rightside = sol.rightSideView(root);
cout << "Printing the right side view of the above tree \n";
for (int x : rightside)
cout << x << " ";
}
/* Practise question link online for reference: https://leetcode.com/problems/binary-tree-right-side-view/ */