199. Binary Tree Right Side View - cocoder39/coco39_LC GitHub Wiki
199. Binary Tree Right Side View
dfs traversal:
- search right subtree first, then left subtree
once found a null node, return
once found the first node in corresponding level, add it into
res
don't terminate dfs when a node is not the right most at this level, since its descending nodes may be right most nodes at certain level.
all nodes would be visited, only right most nodes would be added. O(n) time and O(height) extra space for call stack
class Solution {
public:
vector<int> rightSideView(TreeNode *root) {
vector<int> res;
helper(res, root, 0);
return res;
}
void helper(vector<int> &res, TreeNode* root, int level){
if(! root) {
return;
}
if (res.size() == level) {
res.push_back(root->val);
}
helper(res, root->right, level + 1);
helper(res, root->left, level + 1);
}
};
iterative bfs level order traversal with the help of queue, O(n) time and O(width) space
vector<int> rightSideView(TreeNode* root) {
vector<int> res;
if (! root) {
return res;
}
int level = 0;
queue<TreeNode*> q;
q.push(root);
while (! q.empty()) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
TreeNode* node = q.front();
q.pop();
if (res.size() == level) {
res.push_back(node->val);
}
if (node->right) {
q.push(node->right);
}
if (node->left) {
q.push(node->left);
}
}
level++;
}
return res;
}