Jul 29, 2024 | monday 6:20 pm
This series main purpose is for my own accountability and reference, as well as anyone who wants to follow my journey to becoming a better problem solver. Each week, I will highlight problems that I thought was interesting or difficult. Additionally, other problems that I solved and their solutions are listed below.
MediumBinary-tree
Try it yourself here!
This problem is particularly interesting as it requires a solid understanding of both preorder and inorder traversals to solve effectively. It also provides an excellent opportunity to compare and contrast Depth-First Search (DFS) and Breadth-First Search (BFS) approaches.
BFS (Breadth-First Search): Explores all nodes at the present depth before moving on to nodes at the next depth level. DFS (Depth-First Search): Explores as far as possible along each branch before backtracking.
Problem Statement: The goal is to reconstruct a binary tree using two given lists: one representing the preorder traversal and another representing the inorder traversal of the tree.
Example:
preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7].
The solution can be determined by analyzing both traversal lists:
By combining these properties, we can recursively construct the entire tree.
DFS Algorithm:
Complexity:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
def dfs(left, right):
nonlocal preorder_index
if left > right:
return None
node = preorder[preorder_index]
preorder_index += 1
newNode = TreeNode(node)
newNode.left = dfs(left, indexMap[node] - 1)
newNode.right = dfs(indexMap[node] + 1, right)
return newNode
indexMap = {}
for i, v in enumerate(inorder):
indexMap[v] = i
preorder_index = 0
return dfs(0, len(inorder) - 1)
EasyBinary-tree
Try it yourself here!
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return
left_subtree = self.invertTree(root.left)
right_subtree = self.invertTree(root.right)
root.left = right_subtree
root.right = left_subtree
return root
Complexity:
EasyBinary-tree
Try it yourself here!
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
Complexity:
EasyBinary-tree
Try it yourself here!
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
max_diameter = 0
def getDiameter (root):
nonlocal max_diameter
if not root:
return 0
left_tree = getDiameter(root.left)
right_tree = getDiameter(root.right)
max_diameter = max(max_diameter, left_tree + right_tree)
return 1 + max(left_tree, right_tree)
getDiameter(root)
return max_diameter
Complexity:
EasyBinary-tree
Try it yourself here!
def isBalanced(self, root: Optional[TreeNode]) -> bool:
def balanced(node):
if not node:
return True, -1
isLeftBalanced, leftHeight = balanced(node.left)
if not isLeftBalanced:
return False, 0
isRightBalanced, rightHeight = balanced(node.right)
if not isRightBalanced:
return False, 0
return (abs(rightHeight - leftHeight) < 2), 1 + max(leftHeight, rightHeight)
return balanced(root)[0]
Complexity:
EasyBinary-tree
Try it yourself here!
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
p_queue, q_queue = deque([p]), deque([q])
while p_queue and q_queue:
p_node = p_queue.popleft()
q_node = q_queue.popleft()
if not p_node and not q_node:
continue
if not p_node or not q_node or p_node.val != q_node.val:
return False
p_queue.append(p_node.left)
p_queue.append(p_node.right)
q_queue.append(q_node.left)
q_queue.append(q_node.right)
return len(p_queue) == 0 and len(q_queue) == 0
Complexity:
EasyBinary-tree
Try it yourself here!
def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
def sameTree(p, q):
if not p and not q:
return True
if not p or not q:
return False
return p.val == q.val and sameTree(p.left, q.left) and sameTree(p.right, q.right)
q = deque([root])
while q:
node = q.popleft()
if sameTree(node, subRoot):
return True
if node:
q.append(node.left)
q.append(node.right)
return False
Complexity:
MediumBinary-search-tree
Try it yourself here!
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
node = root
while node:
if p.val > node.val and q.val > node.val:
node = node.right
elif p.val < node.val and q.val < node.val:
node = node.left
else:
return node
Complexity:
MediumBinary-tree
Try it yourself here!
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
q = deque([root])
res = []
while q:
level_length = len(q)
level = []
for _ in range(level_length):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
res.append(level)
return res
Complexity:
MediumBinary-tree
Try it yourself here!
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
ans = []
q = deque([root])
while q:
level_len = len(q)
node = None
for _ in range(level_len):
node = q.popleft()
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
ans.append(node.val)
return ans
Complexity:
MediumBinary-tree
Try it yourself here!
def goodNodes(self, root: TreeNode) -> int:
if root is None:
return 0
count = 0
def findGoodNodes(node, maxSoFar):
nonlocal count
if node.val >= maxSoFar:
count += 1
if node.left:
findGoodNodes(node.left, max(node.val, maxSoFar))
if node.right:
findGoodNodes(node.right, max(node.val, maxSoFar))
findGoodNodes(root, root.val)
return count
Complexity:
MediumBinary-search-tree
Try it yourself here!
def isValidBST(self, root: Optional[TreeNode]) -> bool:
ans = []
def inOrder(node):
if node is None:
return
inOrder(node.left)
ans.append(node.val)
inOrder(node.right)
inOrder(root)
for i in range(1, len(ans)):
if ans[i] <= ans[i - 1]:
return False
return True
Complexity:
MediumBinary-search-tree
Try it yourself here!
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
ans = []
def inOrder(node):
if node is None:
return
inOrder(node.left)
ans.append(node.val)
inOrder(node.right)
inOrder(root)
return ans[k - 1]
Complexity:
HardBinary-tree
Try it yourself here!
def maxPathSum(self, root: Optional[TreeNode]) -> int:
maxSum = float(-inf)
def getSum(node):
nonlocal maxSum
if not node:
return 0
leftMax = max(getSum(node.left), 0)
rightMax = max(getSum(node.right), 0)
maxSum = max(maxSum, leftMax + rightMax + node.val)
return max(leftMax, rightMax) + node.val
getSum(root)
return maxSum
Complexity:
HardBinary-tree
Try it yourself here!
def serialize(self, root):
if root == None: return ""
q = deque([root])
tree = []
while q:
node = q.popleft()
if node:
tree.append(str(node.val))
q.extend([node.left, node.right])
else:
tree.append("*")
return ','.join(tree)
def deserialize(self, data):
if data == "": return None
tree = deque(data.split(","))
root = TreeNode(int(tree.popleft()))
q = deque([root])
while q:
node = q.popleft()
if (left := tree.popleft()) != "*":
node.left = TreeNode(int(left))
q.append(node.left)
if (right := tree.popleft()) != "*":
node.right = TreeNode(int(right))
q.append(node.right)
return root
Complexity: