code: 
  
  """simple docstring"""
  
  
  
  
  from __future__ import annotations
  
  from collections import defaultdict
  from dataclasses import dataclass
  
  
  
  
  
  @dataclass
  class     __UpperCamelCase				:
  		SCREAMING_SNAKE_CASE              =					42
  		SCREAMING_SNAKE_CASE              =					None
  		SCREAMING_SNAKE_CASE              =					None
  
  def      __SCREAMING_SNAKE_CASE		(		):
  					"""simple docstring"""
  					return TreeNode(3    ,							TreeNode(9   )    ,							TreeNode(20    ,							TreeNode(15   )    ,							TreeNode(7   )   )   )
  def      __SCREAMING_SNAKE_CASE		(		lowercase__   ):
  					"""simple docstring"""
  
  					def depth_first_search(
  					    lowercase__    ,							lowercase__    ,							lowercase__   ) -> None:
  										if not root:
  															return
  
  										if depth == len(__lowerCamelCase   ):
  															right_view.append(root.val   )
  
  										depth_first_search(root.right    ,							depth + 1    ,							__lowerCamelCase   )
  										depth_first_search(root.left    ,							depth + 1    ,							__lowerCamelCase   )
  
  					A    =      []
  					if not root:
  										return right_view
  
  					depth_first_search(__lowerCamelCase    ,							0    ,							__lowerCamelCase   )
  					return right_view
  def      __SCREAMING_SNAKE_CASE		(		lowercase__   ):
  					"""simple docstring"""
  
  					def depth_first_search(
  					    lowercase__    ,							lowercase__    ,							lowercase__   ) -> None:
  										if not root:
  															return
  
  										if depth == len(__lowerCamelCase   ):
  															left_view.append(root.val   )
  
  										depth_first_search(root.left    ,							depth + 1    ,							__lowerCamelCase   )
  										depth_first_search(root.right    ,							depth + 1    ,							__lowerCamelCase   )
  
  					A    =      []
  					if not root:
  										return left_view
  
  					depth_first_search(__lowerCamelCase    ,							0    ,							__lowerCamelCase   )
  					return left_view
  def      __SCREAMING_SNAKE_CASE		(		lowercase__   ):
  					"""simple docstring"""
  
  					def breadth_first_search(lowercase__    ,							lowercase__   ) -> None:
  										A    =      [(root, 0)]
  										A    =      defaultdict(__lowerCamelCase   )
  
  										while queue:
  															A    =      queue.pop(0   )
  															A    =      first
  
  															lookup[hd].append(node.val   )
  
  															if node.left:
  																				queue.append((node.left, hd - 1)   )
  															if node.right:
  																				queue.append((node.right, hd + 1)   )
  
  										for pair in sorted(lookup.items()    ,							key=lambda lowercase__   : each[0]   ):
  															top_view.append(pair[1][0]   )
  
  					A    =      []
  					if not root:
  										return top_view
  
  					breadth_first_search(__lowerCamelCase    ,							__lowerCamelCase   )
  					return top_view
  def      __SCREAMING_SNAKE_CASE		(		lowercase__   ):
  					"""simple docstring"""
  					from collections import defaultdict
  
  					def breadth_first_search(lowercase__    ,							lowercase__   ) -> None:
  										A    =      [(root, 0)]
  										A    =      defaultdict(__lowerCamelCase   )
  
  										while queue:
  															A    =      queue.pop(0   )
  															A    =      first
  															lookup[hd].append(node.val   )
  
  															if node.left:
  																				queue.append((node.left, hd - 1)   )
  															if node.right:
  																				queue.append((node.right, hd + 1)   )
  
  										for pair in sorted(lookup.items()    ,							key=lambda lowercase__   : each[0]   ):
  															bottom_view.append(pair[1][-1]   )
  
  					A    =      []
  					if not root:
  										return bottom_view
  
  					breadth_first_search(__lowerCamelCase    ,							__lowerCamelCase   )
  					return bottom_view
  
  
  if __name__ == "__main__":
  	import doctest
  
  	doctest.testmod()
  
  
  
  
  
  
style_context: 
  
  """simple docstring"""
  
  
  
  
  import functools
  from math import sqrt
  from time import time
  def      __SCREAMING_SNAKE_CASE		(		lowercase__    ,							*lowercase__    ,							**lowercase__   ):
  					"""simple docstring"""
  					A    =      time()
  					A    =      func(*lowercase__    ,							**lowercase__   )
  					A    =      time()
  					if int(end - start   ) > 0:
  										print(F"""{func.__name__} runtime: {(end - start):0.4f} s"""   )
  					else:
  										print(F"""{func.__name__} runtime: {(end - start) * 1_000:0.4f} ms"""   )
  					return output
  def      __SCREAMING_SNAKE_CASE		(		lowercase__   ):
  					"""simple docstring"""
  					if n < 0:
  										raise Exception("n is negative"   )
  					if n == 0:
  										return [0]
  					A    =      [0, 1]
  					for _ in range(n - 1   ):
  										fib.append(fib[-1] + fib[-2]   )
  					return fib
  def      __SCREAMING_SNAKE_CASE		(		lowercase__   ):
  					"""simple docstring"""
  
  					def fib_recursive_term(lowercase__   ) -> int:
  										if i < 0:
  															raise Exception("n is negative"   )
  										if i < 2:
  															return i
  										return fib_recursive_term(i - 1   ) + fib_recursive_term(i - 2   )
  
  					if n < 0:
  										raise Exception("n is negative"   )
  					return [fib_recursive_term(lowercase__   ) for i in range(n + 1   )]
  def      __SCREAMING_SNAKE_CASE		(		lowercase__   ):
  					"""simple docstring"""
  
  					@functools.cache
  					def fib_recursive_term(lowercase__   ) -> int:
  										if i < 0:
  															raise Exception("n is negative"   )
  										if i < 2:
  															return i
  										return fib_recursive_term(i - 1   ) + fib_recursive_term(i - 2   )
  
  					if n < 0:
  										raise Exception("n is negative"   )
  					return [fib_recursive_term(lowercase__   ) for i in range(n + 1   )]
  def      __SCREAMING_SNAKE_CASE		(		lowercase__   ):
  					"""simple docstring"""
  					if n < 0:
  										raise Exception("n is negative"   )
  					# Cache must be outside recursuive function
  					# other it will reset every time it calls itself.
  					A    =      {0: 0, 1: 1, 2: 1}  # Prefilled cache
  
  					def rec_fn_memoized(lowercase__   ) -> int:
  										if num in cache:
  															return cache[num]
  
  										A    =      rec_fn_memoized(num - 1   ) + rec_fn_memoized(num - 2   )
  										A    =      value
  										return value
  
  					return [rec_fn_memoized(lowercase__   ) for i in range(n + 1   )]
  def      __SCREAMING_SNAKE_CASE		(		lowercase__   ):
  					"""simple docstring"""
  					if n < 0:
  										raise Exception("n is negative"   )
  					if n >= 1_475:
  										raise Exception("n is too large"   )
  					A    =      sqrt(5   )
  					A    =      (1 + sqrt_a) / 2
  					return [round(phi**i / sqrt_a   ) for i in range(n + 1   )]
  
  
  if __name__ == "__main__":
  	__A  :					Optional[Any]												=	30
  	time_func(fib_iterative, num)
  	time_func(fib_recursive, num)  # Around 3s runtime
  	time_func(fib_recursive_cached, num)  # Around 0ms runtime
  	time_func(fib_memoization, num)
  	time_func(fib_binet, num)
  
  
  
  
  
  