By Long Luo
This article is the solution 2 Approaches: DFS and BFS with Detailed Explanation of Problem 199. Binary Tree Right Side View.
Here shows 2 Approaches to slove this problem: DFS and BFS.
DFS
We traverse the tree in the order of root node→right subtree→left subtree to ensure that each level traverse the rightmost node first.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public List<Integer> rightSideView_dfs(TreeNode root) {
List<Integer> ans = new ArrayList<>();
if (root == null) {
return ans;
}
dfs(root, 1, ans);
return ans;
}
public void dfs(TreeNode root, int depth, List<Integer> numList) {
if (root == null) {
return;
}
if (numList.size() < depth) {
numList.add(root.val);
}
dfs(root.right, depth + 1, numList);
dfs(root.left, depth + 1, numList);
}
|
Analysis
- Time Complexity: O(n)
- Space Complexity: O(n)
BFS
We can use BFS to traverse the levels of the tree and record the last element of each level.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| public List<Integer> rightSideView_bfs(TreeNode root) {
List<Integer> ans = new ArrayList<>();
if (root == null) {
return ans;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = size - 1; i >= 0; i--) {
TreeNode node = queue.poll();
if (i == size - 1) {
ans.add(node.val);
}
if (node.right != null) {
queue.offer(node.right);
}
if (node.left != null) {
queue.offer(node.left);
}
}
}
return ans;
}
|
Analysis
- Time Complexity: O(n).
- Space Complexity: O(n).
All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions. 😉😃💗