Binary Tree Right Side View
Given the root of a binary tree, return the rightmost node value in the nth level, where the root is at level 1 and the rightmost node is at level 1.
Constraints:
- The number of nodes in the tree is in the range [1, 100].
- 1 <= Node.val <= 100
Examples:
Input: [1,2,3,null,5,null,4]
Output: [1,3,4]
Explanation: The rightmost node values in each level are 1, 3, and 4.
Solutions
Breadth-First Search (BFS)
Time: O(N)Space: O(N)
We use a queue to perform a level-order traversal of the binary tree. In each level, we add the rightmost node's value to the result list.
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> result;
if (!root) return result;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int levelSize = q.size();
for (int i = 0;
i < levelSize;
i++) {
TreeNode* node = q.front();
q.pop();
if (i == levelSize - 1) result.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return result;
}
}
;Follow-up:
Can you solve this problem using a recursive approach?
