Sponsored
Sponsored
The Breadth-First Search (BFS) approach involves traversing the tree level by level using a queue. For each level, we capture the last node's value visible when viewed from the right side. This can be done by iterating through each level and storing the value of the last node encountered. This approach ensures that the elements are captured in top-to-bottom order as required.
Time Complexity: O(n), where n is the number of nodes in the tree.
Space Complexity: O(w), where w is the maximum width of the tree (at the level with the most nodes).
1from collections import deque
2
3class TreeNode:
4 def __init__(self, val=0, left=None, right=None):
5 self.val = val
6 self.left = left
7 self.right = right
8
9class Solution:
10 def rightSideView(self, root: TreeNode):
11 if not root:
12 return []
13
14 queue = deque([root])
15 view = []
16
17 while queue:
18 level_length = len(queue)
19 last_node = None
20 for _ in range(level_length):
21 node = queue.popleft()
22 last_node = node.val
23 if node.left:
24 queue.append(node.left)
25 if node.right:
26 queue.append(node.right)
27
28 view.append(last_node)
29
30 return viewThe solution uses a queue to perform BFS. We initialize the queue with the root node, and for each level, we iterate over each node, updating the last node value for that level. At the end of each level iteration, the last node value is added to the result. This gives us the right view of the tree. The space complexity is determined by the maximum width of the tree, and the time complexity is O(n) where n is the number of nodes.
In this approach, a recursive Depth-First Search (DFS) is utilized. It traverses the tree from the root and prioritizes the right child before the left child at each node. By keeping track of the current level, we ensure to capture only the first node visited at that level, which represents the right view at that height.
Time Complexity: O(n), where n is the number of nodes in the tree.
Space Complexity: O(h), where h is the height of the tree, considering the space used for recursion stack.
1#include <vector>
2using namespace std;
3
4struct TreeNode {
5 int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> view;
dfs(root, 0, view);
return view;
}
void dfs(TreeNode* node, int level, vector<int>& view) {
if (!node) return;
if (level == view.size()) view.push_back(node->val);
dfs(node->right, level + 1, view);
dfs(node->left, level + 1, view);
}
};This solution uses DFS, visiting each node starting from the rightmost node. For each node, if it's the first node visited at that level, it gets added to the result, giving the rightmost view.