



"""simple docstring"""




import functools
from math import sqrt
from time import time


def 	lowercase__  (      _UpperCAmelCase						,   *_UpperCAmelCase						,   **_UpperCAmelCase					)  ->      Union[str, Any]:






      '''simple docstring'''


      lowercase	:   Dict											= time()
      lowercase	:   Any											= func(*_UpperCAmelCase						,   **_UpperCAmelCase					)
      lowercase	:   str											= time()
      if int(end - start					) > 0:
            print(f'''{func.__name__} runtime: {(end - start):0.4f} s'''					)
      else:
            print(f'''{func.__name__} runtime: {(end - start) * 10_00:0.4f} ms'''					)
      return output


def 	lowercase__  (      _UpperCAmelCase					)  ->      list[int]:






      '''simple docstring'''


      if n < 0:
            raise Exception('n is negative'					)
      if n == 0:
            return [0]
      lowercase	:   Optional[int]											= [0, 1]
      for _ in range(n - 1					):
            fib.append(fib[-1] + fib[-2]					)
      return fib


def 	lowercase__  (      _UpperCAmelCase					)  ->      list[int]:






      '''simple docstring'''


      def fib_recursive_term(_UpperCAmelCase					) -> 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(_UpperCAmelCase					) for i in range(n + 1					)]


def 	lowercase__  (      _UpperCAmelCase					)  ->      list[int]:






      '''simple docstring'''


      @functools.cache
      def fib_recursive_term(_UpperCAmelCase					) -> 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(_UpperCAmelCase					) for i in range(n + 1					)]


def 	lowercase__  (      _UpperCAmelCase					)  ->      list[int]:






      '''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.
      lowercase	:   dict[int, int]											= {0: 0, 1: 1, 2: 1}  # Prefilled cache

      def rec_fn_memoized(_UpperCAmelCase					) -> int:
            if num in cache:
                  return cache[num]

            lowercase	:   Union[str, Any]											= rec_fn_memoized(num - 1					) + rec_fn_memoized(num - 2					)
            lowercase	:   Tuple											= value
            return value

      return [rec_fn_memoized(_UpperCAmelCase					) for i in range(n + 1					)]


def 	lowercase__  (      _UpperCAmelCase					)  ->      list[int]:






      '''simple docstring'''


      if n < 0:
            raise Exception('n is negative'					)
      if n >= 14_75:
            raise Exception('n is too large'					)
      lowercase	:   Union[str, Any]											= sqrt(5					)
      lowercase	:   Tuple											= (1 + sqrt_a) / 2
      return [round(phi**i / sqrt_a					) for i in range(n + 1					)]


if __name__ == "__main__":
     _UpperCamelCase:					List[Any]     				=	3_0
     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)





"""simple docstring"""




from __future__ import annotations

from collections import defaultdict
from dataclasses import dataclass


@dataclass
class 	a__		:
   _lowerCamelCase       				=					42
   _lowerCamelCase       				=					None
   _lowerCamelCase       				=					None




def 	lowercase__  (      )  ->      TreeNode:






      '''simple docstring'''


      return TreeNode(3						,   TreeNode(9					)						,   TreeNode(20						,   TreeNode(15					)						,   TreeNode(7					)					)					)


def 	lowercase__  (      _UpperCAmelCase					)  ->      list[int]:






      '''simple docstring'''


      def depth_first_search(
          _UpperCAmelCase						,   _UpperCAmelCase						,   _UpperCAmelCase					) -> None:
            if not root:
                  return

            if depth == len(_UpperCAmelCase					):
                  right_view.append(root.val					)

            depth_first_search(root.right						,   depth + 1						,   _UpperCAmelCase					)
            depth_first_search(root.left						,   depth + 1						,   _UpperCAmelCase					)

      lowercase	:   list											= []
      if not root:
            return right_view

      depth_first_search(_UpperCAmelCase						,   0						,   _UpperCAmelCase					)
      return right_view


def 	lowercase__  (      _UpperCAmelCase					)  ->      list[int]:






      '''simple docstring'''


      def depth_first_search(
          _UpperCAmelCase						,   _UpperCAmelCase						,   _UpperCAmelCase					) -> None:
            if not root:
                  return

            if depth == len(_UpperCAmelCase					):
                  left_view.append(root.val					)

            depth_first_search(root.left						,   depth + 1						,   _UpperCAmelCase					)
            depth_first_search(root.right						,   depth + 1						,   _UpperCAmelCase					)

      lowercase	:   list											= []
      if not root:
            return left_view

      depth_first_search(_UpperCAmelCase						,   0						,   _UpperCAmelCase					)
      return left_view


def 	lowercase__  (      _UpperCAmelCase					)  ->      list[int]:






      '''simple docstring'''


      def breadth_first_search(_UpperCAmelCase						,   _UpperCAmelCase					) -> None:
            lowercase	:   List[str]											= [(root, 0)]
            lowercase	:   List[Any]											= defaultdict(_UpperCAmelCase					)

            while queue:
                  lowercase	:   Union[str, Any]											= queue.pop(0					)
                  lowercase						,     lowercase	:   str											= 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 _UpperCAmelCase					: each[0]					):
                  top_view.append(pair[1][0]					)

      lowercase	:   list											= []
      if not root:
            return top_view

      breadth_first_search(_UpperCAmelCase						,   _UpperCAmelCase					)
      return top_view


def 	lowercase__  (      _UpperCAmelCase					)  ->      list[int]:






      '''simple docstring'''


      from collections import defaultdict

      def breadth_first_search(_UpperCAmelCase						,   _UpperCAmelCase					) -> None:
            lowercase	:   Any											= [(root, 0)]
            lowercase	:   Dict											= defaultdict(_UpperCAmelCase					)

            while queue:
                  lowercase	:   str											= queue.pop(0					)
                  lowercase						,     lowercase	:   List[Any]											= 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 _UpperCAmelCase					: each[0]					):
                  bottom_view.append(pair[1][-1]					)

      lowercase	:   list											= []
      if not root:
            return bottom_view

      breadth_first_search(_UpperCAmelCase						,   _UpperCAmelCase					)
      return bottom_view


if __name__ == "__main__":
     import doctest

     doctest.testmod()
