Binary Tree, LeetCode
Full Binary Tree (Proper Binary Tree)
- every node has either exactly two children or no children.
Perfect Binary Tree (Strictly Full Binary Tree):
- Every internal node has two children
- All leaf nodes appear at the same depth(level).
- Level (k) start from 0
- Every level has
2^knodes (Level(k) start from 0). - Total nodes:
2^(k+1) - 1.
- Every level has
- Level (k) start from 1
- Every level has
2^(k - 1). nodes (Level(k) start from 0) - Total nodes:
2^(k) - 1.
- Every level has
Complete Binary Tree:
- Every level, except possibly the last, is completely filled.
- In the last level, all nodes are as far left as possible, with no “gaps” between them.
- heap is a complete binary tree.
Binary Search Tree:
- Average case for search and insert: O(log n) when the tree is approximately balanced (each comparison eliminates about half of the remaining nodes).
- Worst case for search and insert: O(n) if the tree becomes completely unbalanced (degenerates into a chain).
- Left -> Small, Top -> Medium, Right -> Big
- No requirement for node structure
Balanced Binary Search Tree:
- ∀ N: height(N.left) – height(N.right) ≤ 1
- the basic of map and set (the key in map and the element in set is in order)
# Initialization by Linked List:
class ListNode:
def __init__(self, val = 0, left = None, right = None):
self.val = val
self.left = left
self.right = right
# Initialization by List:
list = []
curr: list[index]
left_children: list[2 * index + 1]
right_children: list[2 * index + 2]
Using backtracking to build binary tree
class ListNode:
def __init__(self, val = 0, left = None, right = None):
self.val = val
self.left = left
self.right = right
nums = [1, 2, 3, 4, 5]
def list_to_complete_binary_tree(nums: List[int], i = 0):
if i > len(nums) - 1:
return
node = ListNode(nums[i])
node.left = list_to_complete_binary_tree(nums, i * 2 + 1)
node.right = list_to_complete_binary_tree(nums, i * 2 + 2)
return node
DFS:
# result should be the input of dfs, so that every recursive call will write into the same list
# pre-order
def dfs(self, result, root):
if not root:
return
result.append(root.val) # middle
left_branch = dfs(result, root.left) # left
right_branch = dfs(result, root.right) # right
return result
BFS
from collections import deque
def bfs(self, root):
if not root:
return []
queue = deque([root]) # queue stores node instead of the value of node
result = []
while queue:
length_of_level = len(queue)
level = []
for i in range(length_of_level):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result
144. Binary Tree Preorder Traversal
# 1: _dfs accept result as input
class ListNode:
def __init__(self, val = 0, left = None, right = None):
self.val = val
self.left = left
self.right = right
class Solution:
def preorderTraversal(self, root: Optional[List]) -> List[int]:
return self._dfs(result = [], root = root) if root else []
def _dfs(self, result: List[int], root: Optional[List]) -> List[int]:
if not root:
return # stop iteration
result.append(root.val)
left_branch = self._dfs(result, root.left)
right_branch = self._dfs(result, root.right)
return result
# 2. _dfs doesn't accept result as input
class Solution:
def preorderTraversal(self, root: Optional[List]) -> List[int]:
if not root:
return [] # return value
left = self.preorderTraversal(root.left) # return the value of left_branch
right = self.preorderTraversal(root.right)
return [root.val] + left + right # left and right are all list
145. Binary Tree Postorder Traversal
from typing import Optional, List
class ListNode:
def __ini__(self, val = 0, left = None, right = None):
self.val = val
self.left = left
self.right = right
class Solution:
def postorderTraversal(self, root: Optional[ListNode]) -> ListNode:
if not root:
return []
left = self.postorderTraversal(root.left)
right = self.postorderTraversal(root.right)
return left + right from typing import Optional, List
class ListNode:
def __ini__(self, val = 0, left = None, right = None):
self.val = val
self.left = left
self.right = right
class Solution:
def postorderTraversal(self, root: Optional[ListNode]) -> ListNode:
if not root:
return []
left = self.postorderTraversal(root.left)
right = self.postorderTraversal(root.right)
return left + right + [root.val]
# Or
class Solution:
def postorderTraversal(self, root: Optional[ListNode]) -> ListNode:
return self._dfs(result = [], root = root) if root else [] # in case _dfs only run the first two line code
def _dfs(self, result, root) -> List[int]:
if not root:
return
left_branch = self._dfs(result, root.left)
right_branch = self._dfs(result, root.right)
result.append(root.val)
return result
94. Binary Tree Inorder Traversal
from typing import List, Optional
class ListNode:
def __init__(self, val = 0, left = None, right = None):
self.val = val
self.right = right
self.left = left
class Solution:
def inorderTraversal(self, root: Optional[ListNode]) -> List[int]:
return self._dfs(result = [], root = root) if root else []
def _dfs(self, result, root) -> List[int]:
if not root:
return
left_branch = self._dfs(result, root.left)
result.append(root.val)
right_branch = self._dfs(result, root.right)
return result
# Or
class Solution:
def inorderTraversal(self, root: Optional[ListNode]) -> List[int]:
if not root:
return []
left = self.inorderTraversal(root.left)
right = self.inorderTraversal(root.right)
return left + [root.val] + right
102. Binary Tree Level Order Traversal
class ListNode:
def __init__(self, val = 0, left = None, right = None):
self.val = val
self.left = left
self.right = right
class Solution:
def levelOrder(self, root: Optional[ListNode]) -> List[List[int]]:
if not root:
return []
queue = deque([root])
result = []
while queue:
length_of_level = len(queue)
level = []
for _ in range(length_of_level):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result
from typing import List, Optional
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None # Al
queue = deque([root])
while queue:
node = queue.popleft()
node.left, node.right = node.right, node.left
# Using parallel assignment in python
# temp = node.left
# node.left = node.right
# node.right = temp
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return root
len(nums) is even:
-
len(nums) // 2returns the left middle index. -
math.ceil(nums / 2)returns the right middle index.
len(nums) is odd:
- both return the middle one
queue could also store a tuple (node.left, node.right)
from typing import List, Optional
from collections import deque
class ListNode:
def __init__(self, val = 0, left = None, right = None):
self.val = val
self.left = left
self.right = right
class Solution:
def isSymmetric(self, root: Optional[ListNode]) -> bool:
if not root:
return True
queue = deque([(root.left, root.right)])
while queue:
left, right = queue.popleft()
if not left and not right:
continue
if not left or not right or left.val != right.val:
return False
queue.append((left.left, right.right))
# compare whether the whole tree is symmetric
# queue.append((left.left, left.right)): compare the left branch of left is symmetric or not
queue.append((right.left, left.right))
return True
104. Maximum Depth of Binary Tree
from collections import deque
from typing import Optional
class ListNode:
def __init__(self, val = 0, left = None, right = None):
self.val = val
self.left = left
self.right = right
class Solution:
def maxDepth(self, root: Optional[ListNode]) -> int:
if not root:
return 0
queue = deque([root])
depth = 0
while queue:
depth += 1
length = len(queue)
for _ in range(length):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return depth
# In most problems, it doesn't matter whether
# you place operations like +1, updates,
# or returns at the beginning or end of a loop.
# Confused about the initial value of depth? move the position (beginning is more reasonable)
111. Minimum Depth of Binary Tree
leaf node: both node.left and node.right are None
from collections import deque
from typing import Optional
class ListNode:
def __init__(self, val = 0, left = None, right = None):
self.val = val
self.right = right
self.left = left
class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
queue = deque([root])
depth = 0
while queue:
depth += 1
length = len(queue)
level = []
for _ in range(length):
node = queue.popleft()
if node and not node.left and not node.right:
return depth
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
222. Count Complete Tree Nodes
from collections import deque
from typing import Optional
class ListNode:
def __init__(self, val = 0, left = None, right = None):
self.val = val
self.right = right
self.left = left
class Solution:
def countNodes(self, root: Optional[TreeNode]) -> int:
def getDepth(node):
if not node:
return 0
depth = 0
while node:
depth += 1
node = node.left
if not root:
return 0
depth_of_left_branch = getDepth(root.left) # getDepth is the method in countNodes, no need for self when using getDepth in countNodes
depth_of_right_branch = getDepth(root.right)
if depth_of_left_branch == depth_of_right_branch:
# the left branch is full
return 2^depth_of_left_branch - 1 + 1 + self.countNodes(root.right)
# + 1 is counting node itself
else:
# the right branch is full
return 2^depth_of_right_branch - 1 + 1 + self.counNodes(root.left)
class ListNode:
def __init__(self, val = 0, left = None, right = None):
self.val = val
self.left = left
self.right = right
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
"""
Some changes based on getDepth
def getDepth(node):
if not node:
return 0
left = getDepth(node.left)
# could be filled for the operations on left branch
right = getDepth(node.right)
# could be filled for the operations on right branch
# could be filled for the operation on current node
return max(left, right) + 1
"""
def check(node):
if not node:
return 0
left = check(node.left)
if left == -1:
return -1
right = check(node.right)
if right == -1:
return -1
if abs(left - right) > 1:
return -1
return max(left, right) + 1
return check(root) != -1
Process currnt node
- update the state
- Add the node’s information into global state or the state passed as a parameter.
- path problem: state.path.append(node.val)
- sum problems: state.sum += node.val
- min/max problems: state.best = max(state.best, node.val)
- graph visits: state.visited.add(node)
- Add the node’s information into global state or the state passed as a parameter.
- Check or Record the result
- If the current state meets your goal, then save to your results list and optionally return/prune.
class ListNode: def __init__(self, val = 0, left = None, right = None): self.val = val self.left = left self.right = right class Solution: def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]: paths = [] def _dfs(node, path): if not node: return # ending condition:information to global state if not node.left and not node.right: paths.append(path) return if node.left: _dfs(node.left, path + '->' + str(node.left.val)) if node.right: _dfs(node.right, path + '->' + str(node.right.val)) if root: _dfs(root, str(root.val)) return paths
- If the current state meets your goal, then save to your results list and optionally return/prune.
class ListNode:
def __init__(self, val = 0, left = None, right = None):
self.val = val
self.left = left
self.right = right
class Solution:
def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
_sum = 0
def _dfs(node):
nonlocal _sum
if not node:
return
if node.left and not node.left.left and not node.left.right:
# No matter whether node itself has a right child or not, it does not affect whether node.left is a leaf node.
_sum += node.left.val
_dfs(node.left)
_dfs(node.right)
_dfs(root)
return _sum
513. Find Bottom Left Tree Value
class ListNode:
def __init__(self, val = 0, left = None, right = None):
self.val = val
self.left = left
self.right = right
class Solution:
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
queue = deque([root])
result = []
while queue:
length = len(queue)
level = []
for _ in range(length):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result[-1][0]
Rock find the email
Jeff email
Nacy: linancy@amazon.com
"""
Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".
The testcases will be generated such that the answer is unique.
Example 1:
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.
Example 2:
Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.
Example 3:
Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.
Constraints:
m == s.length
n == t.length
1 <= m, n <= 105
s and t consist of uppercase and lowercase English letters.
Follow up: Could you find an algorithm that runs in O(m + n) time?
"""
"""
sliding window -> iterate the str s
simulate the substring
hashmap -> record the ocurrance of character while doing the iteration
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
need_hashmap = {'A': 1, 'B': 1, 'C': 1}
window = {}
have = 0
required = len(t)
have == testcases
left, right: boundary of window
right -> A (index 0 in s) window['A'] = 1
right -> D (index 1 in s)
right -> B window['B'] = 1
TC: O(len(s) + len(t))
SC:O(max(len(s), len(t)))
"""
from collections import Counter
class Solution:
def minWindow(self, s: str, t: str) -> str:
need_hashmap = Counter(t)
window_hashmap = {}
required_length = len(need_hashmap)
current = 0
left = 0
right = 0
min_length = float('inf')
ans_left, ans_right = 0, 0
while right < len(s):
char = s[right]
if char in need_hashmap:
window_hashmap[char] = window_hashmap.get(char, 0) + 1
if window_hashmap[char] == need_hashmap[char]:
current += 1
while left <= right and current == required_length:
_size = right - left + 1 # right - left -> [left, right)
# update the ans_left, ans_right
if _size < min_length:
min_length = _size
ans_left, ans_right = left, right
left_char = s[left]
# print(left_char)
if left_char in need_hashmap:
window_hashmap[left_char] -= 1
if window_hashmap[left_char] < need_hashmap[left_char]:
current -= 1
left += 1
right += 1
# print(min_length)
return s[ans_left:ans_right + 1] if min_length != float('inf') else ''
solver = Solution()
print('check',solver.minWindow("ADOBECODEBANC", "ABC"))
print('check',solver.minWindow("a", "a"))
print('check',solver.minWindow("a", "aa"))
"""
Number of Paths
You’re testing a new driverless car that is located at the Southwest (bottom-left) corner of an n×n grid. The car is supposed to get to the opposite, Northeast (top-right), corner of the grid. Given n, the size of the grid’s axes, write a function numOfPathsToDest that returns the number of the possible paths the driverless car can take.
the car may move only in the white squares
For convenience, let’s represent every square in the grid as a pair (i,j). The first coordinate in the pair denotes the east-to-west axis, and the second coordinate denotes the south-to-north axis. The initial state of the car is (0,0), and the destination is (n-1,n-1).
The car must abide by the following two rules: it cannot cross the diagonal border. In other words, in every step the position (i,j) needs to maintain i >= j. See the illustration above for n = 5. In every step, it may go one square North (up), or one square East (right), but not both. E.g. if the car is at (3,1), it may go to (3,2) or (4,1).
Explain the correctness of your function, and analyze its time and space complexities.
Example:
5. [N] [N] [N] [N] [ ]
4. [N] [N] [N] [ ] [ ]
3. [N] [N] [ ] [ ] [ ]
2. [N] [ ] [ ] [ ] [ ]
1. [ ] [ ] [ ] [ ] [ ]
0. 1 2 3 4 5
input: n = 4
output: 5 # since there are five possibilities:
# “EEENNN”, “EENENN”, “ENEENN”, “ENENEN”, “EENNEN”,
# where the 'E' character stands for moving one step
# East, and the 'N' character stands for moving one step
# North (so, for instance, the path sequence “EEENNN”
# stands for the following steps that the car took:
# East, East, East, North, North, North)
Constraints:
[time limit] 5000ms
[input] integer n
1 ≤ n ≤ 100
[output] integer
dp[][]
border:
3 [a, b, c, 1]
2 [a, b, 1, d]
1 [a, 1, 2, d]
0 [1, 1, 1, d]
0, 1, 2, 3
n = 4
target: (3, 3)
dp[0][0] = 1
dp[1][0] = 1
dp[1][1] = 1
dp[2][0] = 1
dp[2][1] = dp[1][1] + dp[2][0] = 1 + 1 =2
dp[i][0] = 1 (from (0, 0) to (i, 0))
dp[i][i] = 1 (diagonal)
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[n - 1][n - 1]
"""
def num_of_paths_to_dest(n: int) -> int:
dp = [[0] * n for _ in range(n)]
for i in range(n):
dp[i][0] = 1
dp[i][i] = 1
for i in range(1, n):
for j in range(1, i + 1):
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[n - 1][n - 1]
print(num_of_paths_to_dest(4))
print(num_of_paths_to_dest(3))
print(num_of_paths_to_dest(17))
"""
input: n = 4, 3, 17
output: 5, 2, 35357670
"""
【Attention】Great opportunities from TikTok
Hi Wen,
Hope you are doing well! This is Xuewei from TikTok Talent Acquisition team.
We are opening Software Engineer positions for our TikTok San Jose Office. Please share an updated copy of your resume if you are interested in it!
Look forward to hearing back from you.
Kind regards,
Xuewei Liu
TikTok Acquisition Team
Email: xueweiliu@bytedance.com
https://www.linkedin.com/in/xuewei-liu-03b593334/
Enjoy Reading This Article?
Here are some more articles you might like to read next: