class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
// edge case
vector<int> result;
if(root == NULL) return result;
if(root->left == NULL and root->right == NULL) {
result.push_back(root->val);
return result;
}
// initialize
vector<TreeNode*> queue;
queue.push_back(root);
// regular case, BFS
while(queue.size() != 0) {
int l = queue.size();
for(int i = 0; i < l; i ++) {
root = queue.at(0);
queue.erase(queue.begin());
if(i == 0) result.push_back(root->val);
if(root->right != NULL) queue.push_back(root->right);
if(root->left != NULL) queue.push_back(root->left);
}
}
return result;
}
};
Time complexity = O(n) , space complexity = O(n) , 这里的空间复杂度是额外定义的队的大小,最大为 n . n是总共的节点数。