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) {
if (root == nullptr) {
return {};
}
vector<int> right_view_nodes;
queue<TreeNode *> level_nodes{{root}};
while (!level_nodes.empty()) {
int node_count = level_nodes.size();
for (int i = 0; i < node_count; ++i) {
auto node = level_nodes.front();
level_nodes.pop();
if (node->left != nullptr) {
level_nodes.push(node->left);
}
if (node->right != nullptr) {
level_nodes.push(node->right);
}
if (i == node_count - 1) {
right_view_nodes.push_back(node->val);
}
}
}
return right_view_nodes;
}
};