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.

Example:

Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

// Iteration
vector<int> rightSideView(TreeNode* root) { // time: O(n); space: O(h)
    vector<int> res;
    if (!root) return res;
    queue<TreeNode*> q({root});
    while (!q.empty()) {
        for (int i = q.size() - 1; i >= 0; --i) {
            TreeNode* t = q.front(); q.pop();
            if (t->left) q.push(t->left);
            if (t->right) q.push(t->right);
            if (i == 0) res.push_back(t->val);
        }
    }
    return res;
}

// Recursion
void helper(TreeNode* node, int level, vector<int>& res) {
    if (!node) return;
    if (res.size() == level) res.push_back(node->val);
    helper(node->right, level + 1, res);
    helper(node->left, level + 1, res);
}
vector<int> rightSideView(TreeNode* root) { // time: O(n); space: O(h)
    vector<int> res;
    helper(root, 0, res);
    return res;
}