Posts

Problem Statement Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1. You must write an algorithm with O(log n) runtime complexity. Example 1: Input: nums = [-1,0,3,5,9,12], target = 9 Output: 4 Explanation: 9 exists in nums and its index is 4 Example 2: Input: nums = [-1,0,3,5,9,12], target = 2 Output: -1 Explanation: 2 does not exist in nums so return -1 Solution class Solution: def search(self, nums: List[int], target: int) -> int: """ 0 1 2 3 4 5 ---------------------- / target -1, 0, 3, 5, 9, 12 ^a ^m ^b """ a, b = 0, len(nums) - 1 while a <= b: m = (b + a) // 2 if nums[m] == target: return m elif nums[m] < target: a = m + 1 else: b = m - 1 return -1 Leetcode 704 Binary Search

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

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

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

1. Full (Proper) Binary Tree # Each nodes has either 2 or 0 children. 12 8 18 5 11 2. Degenerate (Pathological) Binary Tree # Each internal node has either a right or a left child. # Each node is a left node or each node is a right node. 1 1 2 2 3 3 4. Complete Binary Tree # Each level is filled from left to right. 8 5 3 4 6 7 5....