[LeetCode][199. Binary Tree Right Side View] 2 Approaches: DFS and BFS with Detailed Explanation

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 1.6k 阅读时长 ≈ 1 分钟

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 \(\textit{root node} \to \textit{right subtree} \to \textit{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. 😉😃💗