Recursive

Leetcode 70: Climbing Stairs

Problem Statement Description You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Examples Example 1: Input: n = 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps Example 2: Input: n = 3 Output: 3 Explanation: There are three ways to climb to the top....

Leetcode 236 Lowest Common Ancestor of a Binary Tree

Introduction Daniel (🧔🏽‍♂️) nodded his head slowly as he added cream to his freshly poured coffee. He had worked hard to learn his Leetcode and he was feeling ready. He took a sip and walked over to his laptop and sat down. Moments later the interview began. 👩 “Good afternoon Daniel! Thanks for taking the time to interview with me today. Let’s begin with some brief introductions. My name is Jordanna!...

Binary Tree: Postorder Traversal

Tree Node Definition # Definition for a binary tree node. from typing import List class TreeNode: def __init__(self, x: int) -> None: self.val = x self.left = None self.right = None Recursive Implementation left ➡️ right ➡️ root class Solution: def traversal(self, root: 'TreeNode', result=None) -> List[List[int]]: """ 0 / \ 1 2 / \ 3 4 / \ 6 9 Post-order...: [3, 6, 9, 4, 1, 2, 0] T: O(N) S: O(N) worst case; O(log N) average """ if result is None: result = [] if not root: return [] self....

Binary Tree: Inorder Traversal

Tree Node Definition # Definition for a binary tree node. from typing import List class TreeNode: def __init__(self, x: int) -> None: self.val = x self.left = None self.right = None Recursive Implementation left ➡️ root ➡️ right class Solution: def traversal(self, root: 'TreeNode', result=None) -> List[List[int]]: """ 0 / \ 1 2 / \ 3 4 / \ 6 9 In-order...: [3, 1, 6, 4, 9, 0, 2] T: O(N) S: O(N) worst case; O(log N) average """ if result is None: result = [] if not root: return [] self....

Binary Tree: Preorder Traversal

Tree Node Definition # Definition for a binary tree node. from typing import List class TreeNode: def __init__(self, x: int) -> None: self.val = x self.left = None self.right = None Recursive Implementation root ➡️ left ➡️ right class Solution: def traversal(self, root: 'TreeNode', ans=None) -> List[List[int]]: """ 0 / \ 1 2 / \ 3 4 / \ 6 9 Pre-order...: [0, 1, 3, 4, 5, 9, 2] """ if not root: return [] if ans is None: ans = [] ans....