commit fe75d78dc5802107587993036061f9e2d99b9d0e
parent bca0cf9d05d7ff5f77d552eb6fb56bacff8190c3
Author: Andrew Laack <andrew@laack.co>
Date: Tue, 24 Jun 2025 09:45:28 -0500
Completed 5 more lc problems
Diffstat:
5 files changed, 149 insertions(+), 0 deletions(-)
diff --git a/diameter-of-binary-tree/diameter-binary-tree.py b/diameter-of-binary-tree/diameter-binary-tree.py
@@ -0,0 +1,45 @@
+# Definition for a binary tree node.
+# class TreeNode:
+# def __init__(self, val=0, left=None, right=None):
+# self.val = val
+# self.left = left
+# self.right = right
+
+# addl : right_height
+# addl : left_height
+
+# Idea:
+
+# Find height of left and right at each node.
+# Return this up the stack. Incrementing longest as we return.
+
+# for each element, we then sum left and right heights and return largest one.
+
+class Solution:
+ def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
+
+ if root.left is None and root.right is None:
+ return 0
+
+ return get_heights(root)[1]
+
+# TUPLE:
+# [0] is the number of traversals to the bottom
+# [1] is the max traversals in the tree
+
+def get_heights(node : TreeNode):
+ if node is None:
+ return [-1,0]
+
+ left_tuple = get_heights(node.left)
+ right_tuple = get_heights(node.right)
+
+ lh = left_tuple[0] + 1
+ rh = right_tuple[0] + 1
+
+ node.left_height = lh
+ node.right_height = rh
+
+ current = lh + rh
+
+ return max(lh,rh), max(current, left_tuple[1], right_tuple[1])
diff --git a/find-the-duplicate-number/find-duplicate.py b/find-the-duplicate-number/find-duplicate.py
@@ -0,0 +1,16 @@
+class Solution:
+
+ # negate the index for each number
+ # if we find an index has already been
+ # negated, this is duplicate.
+
+ def findDuplicate(self, nums: List[int]) -> int:
+
+ for num in nums:
+ index = abs(num) - 1
+ if nums[index] < 0:
+ return index + 1
+ else:
+ nums[index] *= -1
+
+ return -1
diff --git a/invert-binary-tree/invert-binary-tree.py b/invert-binary-tree/invert-binary-tree.py
@@ -0,0 +1,31 @@
+# Definition for a binary tree node.
+# 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 root is None:
+ return root
+
+ out = recurse(root)
+ return out
+
+def recurse(current):
+
+ assert(current is not None)
+
+ if current.left is None and current.right is None:
+ return current
+
+ temp = current.right
+ current.right = current.left
+ current.left = temp
+
+ if current.left is not None:
+ recurse(current.left)
+ if current.right is not None:
+ recurse(current.right)
+ return current
diff --git a/maximum-depth/maximum-depth.py b/maximum-depth/maximum-depth.py
@@ -0,0 +1,19 @@
+# Definition for a binary tree node.
+# class TreeNode:
+# 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[TreeNode]) -> int:
+ return dfs(root, 0)
+
+def dfs(current, depth) -> int:
+
+ if current is None:
+ return depth
+
+ left = dfs(current.left, depth + 1)
+ right = dfs(current.right, depth + 1)
+
+ return max(left,right)
diff --git a/remove-nth-node-from-end/remove-nth.py b/remove-nth-node-from-end/remove-nth.py
@@ -0,0 +1,38 @@
+# Definition for singly-linked list.
+# class ListNode:
+# def __init__(self, val=0, next=None):
+# self.val = val
+# self.next = next
+class Solution:
+ def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
+
+ #############################################
+
+ # IDEA:
+
+ # two pointers, sliding window
+ # left_ptr = right_ptr's index - (n + 1)
+ # right_ptr increments until reaching the end
+ # once right_ptr is at the end, left_ptr is one position before the point to remove
+ # at this point, we set left_ptr's next to be left_ptr.next.next.
+
+ #############################################
+
+ if head.next is None:
+ return None
+
+ left_node = head
+ right_node = head
+
+ for i in range(0, n):
+ right_node = right_node.next
+
+ if right_node is None:
+ return head.next
+
+ while right_node.next is not None:
+ right_node = right_node.next
+ left_node = left_node.next
+
+ left_node.next = left_node.next.next
+ return head
