199. Binary Tree Right Side View
1. Description
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.
2. Example
Example 1
Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]
Explanation:
Example 2
Input: root = [1,2,3,4,null,null,null,5]
Output: [1,3,4,5]
Explanation:
Example 3
Input: root = [1,null,3]
Output: [1,3]
Example 4
Input: root = []
Output: []
3. Constraints
- The number of nodes in the tree is in the range [0, 100].
- -100 <= Node.val <= 100
4. Solutions
Breadth-first Search
n is the number of nodes in root
Time complexity: O(n)
Space complexity: O(n)
class Solution {
public:
vector<int> rightSideView(TreeNode *root) {
vector<int> right_view_values;
if (root == nullptr) {
return right_view_values;
}
queue<TreeNode *> level_nodes{{root}};
while (!level_nodes.empty()) {
const int n = level_nodes.size();
int value = 0;
for (int i = 0; i < n; ++i) {
TreeNode *node = level_nodes.front();
level_nodes.pop();
value = node->val;
if (node->left != nullptr) {
level_nodes.push(node->left);
}
if (node->right != nullptr) {
level_nodes.push(node->right);
}
}
right_view_values.push_back(value);
}
return right_view_values;
}
};