Aug 10, 2021

Leetcode 199 Binary Tree Right Side View





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

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

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.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    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)