[LeetCode] 199. Binary Tree Right Side View

1. Question

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example 1:

Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]

Example 2:

Input: root = [1,null,3]
Output: [1,3]

Example 3:

Input: root = []
Output: []

2. Thoughts

Use BFS.
1. Iterate through every level of the tree.
2. append the last element of the level.
3. return list

3. Tips learned

4. My solution

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        tree = deque([root])
        result = []

        while tree:
            level = len(tree)
            for _ in range(level - 1):
                node = tree.popleft()
                if node.left:
                    tree.append(node.left)
                if node.right:
                    tree.append(node.right)

            rightmost_node = tree.popleft()
            result.append(rightmost_node.val)
            if rightmost_node.left:
                tree.append(rightmost_node.left)
            if rightmost_node.right:
                tree.append(rightmost_node.right)

        return result

216/216 cases passed (34 ms)
Your runtime beats 89.47 % of python3 submissions
Your memory usage beats 80.22 % of python3 submissions (16.2 MB)

5. AI Solution and Improvements

Your solution to the problem of finding the right side view of a binary tree is quite efficient and follows a standard Breadth-First Search (BFS) approach using a queue (in Python, a deque). However, there is a small optimization that can be made to simplify the code and potentially improve its readability and performance.

In your current implementation, you are iterating over each level of the tree and then handling the rightmost node separately. This can be simplified by directly accessing the rightmost node at each level, as it is the last node in the queue for that level. Here's how you can modify your code:

from collections import deque

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        queue = deque([root])
        result = []

        while queue:
            level_length = len(queue)
            for i in range(level_length):
                node = queue.popleft()
                if i == level_length - 1:
                    # Add the last node of each level to the result
                    result.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

        return result

In this revised version, the key change is that instead of handling the rightmost node outside the for loop, you identify it as the last node in the current level (when i == level_length - 1) and add it to the result list. This approach eliminates the need for a separate handling of the rightmost node and makes the code more concise and potentially faster due to fewer operations within the loop.