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. 😉😃💗