Leetcode 199. Binary Tree Right Side View (Python)

Related Topic

Depth-First-Search. Tree.

Description

Given 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.

Sample I/O

Example 1

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

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

Methodology

This question can be solved by Depth First Search

When you standing on the right side, the number of the nodes you can see is the height of the tree. Now, we need to know the height of the tree. With height, we need to find the farthest to right nodes for each level.

Code

def rightSideView(self, root: TreeNode) -> List[int]:
        def dfs(root, result_list, level):
            if not root:
                return
            if root and level == len(result_list):
                result_list.append(root.val)
            dfs(root.right, result_list, level+1)
            dfs(root.left, result_list, level+1)
            return result_list
        return dfs(root, [], 0)

BigO

We traversal all nodes of the tree once so the time complexity is O(n)