Dare2Solve
Given the root of a binary tree, the task is to return the values of the nodes you can see ordered from top to bottom when looking at the tree from the right side.
The right side view of a binary tree can be obtained by performing a level-order traversal (BFS) of the tree and capturing the last node's value at each level. Since we are interested in the rightmost nodes, traversing each level and noting the last node will provide the right side view.
O(n), where n is the number of nodes in the tree. Each node is processed once.
O(n), due to the space required to store the nodes in the queue.
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> result;
if (!root) return result;
queue<TreeNode*> queue;
queue.push(root);
while (!queue.empty()) {
int n = queue.size();
vector<int> values;
for (int i = 0; i < n; ++i) {
TreeNode* node = queue.front();
queue.pop();
if (node->left) queue.push(node->left);
if (node->right) queue.push(node->right);
values.push_back(node->val);
}
result.push_back(values.back());
}
return result;
}
};
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
result = []
if not root:
return result
queue = deque([root])
while queue:
level_length = len(queue)
for i in range(level_length):
node = queue.popleft()
if i == level_length - 1:
result.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int n = queue.size();
List<Integer> values = new ArrayList<>();
for (int i = 0; i < n; i++) {
TreeNode node = queue.poll();
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
values.add(node.val);
}
result.add(values.get(values.size() - 1));
}
return result;
}
}
var rightSideView = function (root)
{
if (!root) return [];
let result = [];
let queue = [];
queue.push(root)
while (queue.length) {
let values = []
let n = queue.length;
for (let i = 0; i < n; i++) {
let node = queue.shift();
if (root) {
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
values.push(node.val);
}
}
console.log(values)
result.push(values.pop());
}
return result;
};