-
Notifications
You must be signed in to change notification settings - Fork 0
/
binary_tree_right_side_view.cpp
75 lines (68 loc) · 1.85 KB
/
binary_tree_right_side_view.cpp
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
// =====================================================================================
//
// Filename: binary_tree_right_side_view.cpp
//
// Description: 199. Binary Tree Right Side View. Given 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.
//
// Version: 1.0
// Created: 09/11/2019 07:47:47 PM
// Revision: none
// Compiler: g++
//
// Author: Zhu Xianfeng (), [email protected]
// Organization:
//
// =====================================================================================
#include <stdio.h>
#include <queue>
#include <vector>
struct TreeNode
{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution
{
public:
std::vector<int> rightSideView(TreeNode* root)
{
if (root == nullptr)
{
return std::vector<int>();
}
std::vector<int> values;
std::queue<TreeNode*> nodes;
nodes.push(root);
while (!nodes.empty())
{
values.push_back(nodes.back()->val);
int len = nodes.size();
while (len > 0)
{
auto* cur = nodes.front();
if (cur->left != nullptr)
{
nodes.push(cur->left);
}
if (cur->right != nullptr)
{
nodes.push(cur->right);
}
nodes.pop();
len--;
}
}
return values;
}
};
int main(int argc, char* argv[])
{
TreeNode* root = nullptr;
auto values = Solution().rightSideView(root);
printf("Tree's height = %lu\n", values.size());
return 0;
}