Completed Data Structure I

Interstellarkai · Jun 11, 2022 · 9c86cb5 · 9c86cb5
1 parent e9bb0ad
commit 9c86cb5
Show file tree

Hide file tree

Showing 14 changed files with 995 additions and 42 deletions.
diff --git a/Data Structure I/101.symmetric-tree.py b/Data Structure I/101.symmetric-tree.py
@@ -0,0 +1,61 @@
+#
+# @lc app=leetcode id=101 lang=python3
+#
+# [101] Symmetric Tree
+#
+
+# @lc code=start
+# 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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
+        def dfs(left_node, right_node):
+            if not left_node and not right_node:
+                return True
+
+            if not left_node or not right_node:
+                return False
+
+            if left_node.val != right_node.val:
+                return False
+
+            return dfs(left_node.left, right_node.right) and dfs(left_node.right, right_node.left)
+
+        return dfs(root, root)
+
+
+
+
+    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
+        """
+        Iterative DFS approach
+        Using Stack
+        T: O(V+E) 36.80% | 53ms
+        S: O(L) 93.90% | 13.9mb
+        """
+        if root is None:
+            return True
+        stack = [(root.left, root.right)]
+        while stack:
+            left, right = stack.pop()
+            # Check
+            if left is None and right is None:
+                continue
+            # Check
+            if left is None or right is None:
+                return False
+            # Check
+            if left.val != right.val:
+                return False
+            # Appending
+            stack.append((left.left, right.right))
+            stack.append((left.right, right.left))
+        return True
+
+
+# @lc code=end
diff --git a/Data Structure I/102.binary-tree-level-order-traversal.py b/Data Structure I/102.binary-tree-level-order-traversal.py
@@ -0,0 +1,67 @@
+#
+# @lc app=leetcode id=102 lang=python3
+#
+# [102] Binary Tree Level Order Traversal
+#
+
+# @lc code=start
+# 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 levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
+        """
+        Concept: Breadth First Search, requires a Queue
+        T : O(V+E) 17.73% | 64ms
+        S : O(L) 83.11% | 14.1mb
+        """
+        # Sanity Check
+        if not root:
+            return []
+
+        # Initialize
+        result, queue = [], [root]
+
+        while queue:
+            level = []
+            for _ in range(len(queue)):  # Explore current level
+                node = queue.pop(0)  # dequeue current level node
+                level.append(node.val)
+                if node.left:
+                    queue.append(node.left)  # enqueue child node
+                if node.right:
+                    queue.append(node.right)  # enqueue child node
+            # Insert this level to result
+            result.append(level)
+        return result
+
+    def levelOrder(self, root: TreeNode) -> List[List[int]]:
+        """
+        We should not use pop(0), therefore it costs O(n).
+        T : O(V+E) 46.19% | 50ms
+        S : O(L) 83.11% | 14.1mb
+        """
+        if not root:
+            return []
+
+        result: List[List[int]] = []
+        lay = [root]
+        while lay:
+            lay_values = []
+            next_lay = []
+
+            for node in lay:
+                lay_values.append(node.val)
+                if node.left:
+                    next_lay.append(node.left)
+                if node.right:
+                    next_lay.append(node.right)
+
+            lay = next_lay
+            result.append(lay_values)
+
+        return result
+# @lc code=end
diff --git a/Data Structure I/104.maximum-depth-of-binary-tree.py b/Data Structure I/104.maximum-depth-of-binary-tree.py
@@ -0,0 +1,80 @@
+#
+# @lc app=leetcode id=104 lang=python3
+#
+# [104] Maximum Depth of Binary Tree
+#
+
+# @lc code=start
+# 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
+from urllib.parse import non_hierarchical
+
+
+class Solution:
+    def maxDepth(self, root: Optional[TreeNode]) -> int:
+        """
+        Recursion approach
+        T : O(V+E) 57.75% | 54ms
+        S : O(H) + Call Stacks 22.70% | 16.3mb
+        """
+        if root is None:
+            return 0
+        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
+
+    def maxDepth(self, root: Optional[TreeNode]) -> int:
+        """
+        Iterative DFS approach
+        Using Stack
+        T: O(V+E) 48.52% | 58ms
+        S: O(H) 89.96% | 15.3mb
+        """
+        # Sanity Check
+        if root is None:
+            return 0
+        # Initialize
+        stack = [(root, 1)]
+        max_depth = 0
+        # Main
+        while stack:
+            node, depth = stack.pop()
+            max_depth = max(max_depth, depth)
+            if node.right:
+                stack.append((node.right, depth + 1))
+            if node.left:
+                stack.append((node.left, depth + 1))
+            # This method will yields '+1' another time because stacks has none as child nodes
+            # if node:
+            #     stack.append((node.right, depth + 1))
+            #     stack.append((node.left, depth + 1))
+        return max_depth
+
+    def maxDepth(self, root: Optional[TreeNode]) -> int:
+        """
+        Iterative BFS approach
+        Using Queue
+        T: O(V+E) 9.85% | 83ms
+        S: O(L) 98.72% | 15.2mb
+        """
+        # Sanity Check
+        if root is None:
+            return 0
+        # Initialize
+        max_depth = 0
+        queue = [root]
+        # Main
+        while queue:
+            max_depth += 1
+            for _ in range(len(queue)): # Clear level at this time capture (cannot do for node in queue)
+                node = queue.pop(0)
+                if node.left:
+                    queue.append(node.left) # Append next level child nodes
+                if node.right:
+                    queue.append(node.right) # Append next level child nodes
+        return max_depth
+
+# @lc code=end
+
diff --git a/Data Structure I/112.path-sum.py b/Data Structure I/112.path-sum.py
@@ -0,0 +1,59 @@
+#
+# @lc app=leetcode id=112 lang=python3
+#
+# [112] Path Sum
+#
+
+# @lc code=start
+# 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
+        """
+        T : O(V+E) 22.00% | 75ms
+        S : O(H) 57.50% | 15mb
+        """
+        # Sanity Check
+        if root is None:
+            return False
+        # Leaf node
+        if not (root.left or root.right):
+            return root.val == targetSum
+        # Recursion - preorder traversal
+        return self.hasPathSum(root.left, targetSum - root.val) or self.hasPathSum(root.right, targetSum - root.val)
+
+    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
+        """
+        T : O(V+E) 99.99%
+        S : O(H)
+        """
+        if root == None:
+            return False
+        targetSum = targetSum - root.val
+        if (targetSum == 0) and root.left == None and root.right == None:
+            return True
+        return self.hasPathSum(root.left, targetSum) or self.hasPathSum(root.right, targetSum)
+
+    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
+        """
+        Stack Method
+        T : O(V+E) 43.65% | 62ms
+        S : O(H) 57.50% | 15.1mb
+        """
+        if not root:
+            return False
+        stack = [(root, root.val)]
+        while stack:
+            node, val = stack.pop()
+            if not node.left and not node.right and val == targetSum:
+                return True
+            if node.right:
+                stack.append((node.right, val + node.right.val))
+            if node.left:
+                stack.append((node.left, val + node.left.val))
+        return False
+# @lc code=end
diff --git a/Data Structure I/144.binary-tree-preorder-traversal.py b/Data Structure I/144.binary-tree-preorder-traversal.py
@@ -0,0 +1,91 @@
+#
+# @lc app=leetcode id=144 lang=python3
+#
+# [144] Binary Tree Preorder Traversal
+#
+
+# @lc code=start
+# 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
+        """
+        Preorder Traversal is first visit. Once a node is touched, print it.
+        Recursive
+        T : O(V+E) 63.29% | 38ms, little recursion overhead
+        S : O(H) 58.51% | 13.8mb, recursive call consumes stack space
+        """
+
+        # Sanity Check
+        if root is None:
+            return []
+
+        # Main
+        result = []
+        result.append(root.val)
+
+        if root.left:
+            result += self.preorderTraversal(root.left)
+        if root.right:
+            result += self.preorderTraversal(root.right)
+
+        return result
+
+    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
+        return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right) if root else []
+
+    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
+        """
+        Preorder Traversal is first visit. Once a node is touched, print it.
+
+        Preorder, Inorder, Postorder
+            - DFS
+            - Stack -> LIFO
+
+        Iterative
+        T : O(V+E) 16.93% | 56 ms
+        S : O(H) 96.64% | 13.8mb better because of less stack space
+        """
+
+        # Sanity Check
+        if root is None:
+            return
+
+        # Initialize
+        stack = [root]  # For tranversing
+        result = []  # To store returning result
+
+        # Main
+        while stack:
+            node = stack.pop()
+            result.append(node.val)
+            if node.right:
+                stack.append(node.right)
+            if node.left:
+                stack.append(node.left)
+
+        # Would be faster to do this instead.
+            # node = stack.pop()
+            # if node:
+            #     stack.append(node.right)
+            #     stack.append(node.left)
+            #     result.append(node.val)
+        return result
+
+    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
+        res, stack = [], [(root, False)]
+        while stack:
+            node, visited = stack.pop()  # the last element
+            if node:
+                if visited:
+                    res.append(node.val)
+                else:  # preorder: root -> left -> right
+                    stack.append((node.right, False))
+                    stack.append((node.left, False))
+                    stack.append((node, True))
+        return res
+# @lc code=end