1+ // Source : https://leetcode.com/problems/binary-tree-right-side-view/
2+ // Author : David Lin
3+ // Date : 2023-05-18
4+
5+ /* *********************************************************************************
6+ *
7+ * Given a binary tree, imagine yourself standing on the right side of it, return
8+ * the values of the nodes you can see ordered from top to bottom.
9+ *
10+ * For example:
11+ * Given the following binary tree,
12+ *
13+ * 1 <---
14+ * / \
15+ * 2 3 <---
16+ * \ \
17+ * 5 4 <---
18+ *
19+ * You should return [1, 3, 4].
20+ *
21+ *
22+ *
23+ **********************************************************************************/
24+ #include < stdio.h>
25+ #include < stdlib.h>
26+ #include < time.h>
27+ #include < iostream>
28+ #include < vector>
29+ #include < queue>
30+
31+ using namespace std ;
32+
33+
34+ struct TreeNode {
35+ int val;
36+ TreeNode *left;
37+ TreeNode *right;
38+ TreeNode (int x) : val(x), left(NULL ), right(NULL ) {}
39+ };
40+
41+
42+ void printTree (TreeNode *root)
43+ {
44+ if (root == NULL ){
45+ printf (" # "
46+ return ;
47+ }
48+ printf (" %d " val );
49+
50+ printTree (root->left );
51+ printTree (root->right );
52+ }
53+
54+
55+ void printTree_level_order (TreeNode *root)
56+ {
57+ queue<TreeNode*> q;
58+ q.push (root);
59+ while (q.size ()>0 ){
60+ TreeNode* n = q.front ();
61+ q.pop ();
62+ if (n==NULL ){
63+ cout << " # "
64+ continue ;
65+ }
66+ cout << n->val << " "
67+ q.push (n->left );
68+ q.push (n->right );
69+ }
70+ cout << endl;
71+ }
72+
73+
74+ TreeNode* createTree (int a[], int n)
75+ {
76+ if (n<=0 ) return NULL ;
77+
78+ TreeNode **tree = new TreeNode*[n];
79+
80+ for (int i=0 ; i<n; i++) {
81+ if (a[i]==0 ){
82+ tree[i] = NULL ;
83+ continue ;
84+ }
85+ tree[i] = new TreeNode (a[i]);
86+ }
87+ int pos=1 ;
88+ for (int i=0 ; i<n && pos<n; i++) {
89+ if (tree[i]){
90+ tree[i]->left = tree[pos++];
91+ if (pos<n){
92+ tree[i]->right = tree[pos++];
93+ }
94+ }
95+ }
96+ return tree[0 ];
97+ }
98+
99+
100+ void printMatrix (vector<int > &vv)
101+ { cout << " ["
102+ for (int i=0 ; i<vv.size (); i++) {
103+
104+
105+ cout << " "
106+
107+
108+ }
109+ cout << " ]"
110+ }
111+
112+
113+ vector<int > rightSideView (TreeNode *root) {
114+ vector<int > Results;
115+ if (!root) return Results;
116+ queue<TreeNode*> q;
117+ q.push (root);
118+ while (!q.empty ())
119+ {
120+ int length = q.size ();
121+ int count{};
122+ while (count < length)
123+ {
124+ TreeNode* p = q.front ();
125+ q.pop ();
126+ if (count == length - 1 ) Results.push_back (p->val );
127+ if (p->left ) q.push (p->left );
128+ if (p->right ) q.push (p->right );
129+ count += 1 ;
130+
131+ }
132+
133+ }
134+ return Results;
135+ }
136+
137+
138+ void dfs (TreeNode* root, int level, vector<int >& Result){
139+ if (level == Result.size ()) {
140+ Result.push_back (root->val );
141+ }
142+ /* printMatrix(Result); */
143+ if (root->right ){
144+ dfs (root->right , level+1 , Result);
145+ }
146+ if (root->left ){
147+ dfs (root->left , level+1 , Result);
148+ }
149+ }
150+
151+
152+ vector<int > rightSideView2 (TreeNode *root){
153+ vector<int > Result;
154+ if (!root) return Result;
155+ int level;
156+ dfs (root, level, Result);
157+ /* printMatrix(Result); */
158+ return Result;
159+
160+ }
161+
162+
163+ int main ()
164+ {
165+ TreeNode *p;
166+ vector<int > vv;
167+
168+ int a[] = {1 ,2 ,3 ,0 ,5 ,0 ,4 };
169+ p = createTree (a, sizeof (a)/sizeof (int ));
170+ printTree_level_order (p);
171+ vv = rightSideView (p);
172+ printMatrix (vv);
173+ cout << endl;
174+
175+ int b[] = {1 ,2 ,3 ,0 ,5 ,0 ,4 };
176+ p = createTree (b, sizeof (b)/sizeof (int ));
177+ printTree_level_order (p);
178+ vv = rightSideView2 (p);
179+ printMatrix (vv);
180+ cout << endl;
181+ }
0 commit comments