-
LeetCode 108: Convert Sorted Array to Binary Search Tree
link Recursive Like binary search, we recursively make mid the root and mid‘s left and right sub-lists the left and right subtrees. Time: There are levels and due to slicing, each level has copies. So, like merge-sort, total time is . Space: . Slicing is not necessary, we could pass around (lo, hi) — significantly…
-
LeetCode 124: Binary Tree Maximum Path Sum
link Recursive In the binary tree, there are two types of path: (1) linear (2) curved. Sum on a linear path may contribute to parent’s sum. Sum on a curved path does not contribute to parent’s sum. Say is the linear sum of the node — sum on a linear path that ends at .…
-
LeetCode 226: Invert Binary Tree
link Recursive We swap the children recursively, bottom-up. Time: , space: . Or, top-down: Iterative With stack, we simulate top-down swaps.
-
Binary Tree
Special type of directed graph where a node can have at most two outgoing edges and one incoming edge. Unlike graphs, with a binary tree, we differentiate between the two outgoing edges by marking one as left and the other as right. Test helpers Height Height of a node : Height is the count of…
-
LeetCode 297: Serialize and Deserialize Binary Tree
link Recursive We serialize the tree in pre-order like: . During deserialization, we use a stack to parse nested parentheses or brackets. Time: , space: . With preorder as: , we can deserialize more tersely using recursion: Iterative With levelwise travesal, we can (de)serialize iteratively. We use “” as a serialization for None. During serialization,…
-
LeetCode 543: Diameter of Binary Tree
link Recursive Diameter is the edge count along the longest path. The longest path going through a node can have parts from both left and right subtrees. It is hard to define diameter going through a node in terms of diameter of its children. . However, it is easy to define in terms of height…
-
LeetCode 114: Flatten Binary Tree to Linked List
link Recursive A flattened list has a head and a tail. We recursively flatten root.left and root.right and then combine the flattened sublists to build a longer list: root -> flattened_left -> flattened_right. Time: , space: Root becomes the head of the flattened list, so we do not need to keep track of head of…
-
LeetCode 1380: Lucky Numbers in a Matrix
link A lucky number is both a row min and a column max. We find the row mins and column maxes in one pass and return their overlap as the lucky numbers. Time: , space: . O(1) extra space: reuse matrix If modifying the matrix is feasible, we could use the first row to save…
-
LeetCode 1791: Find Center of Star Graph
link In-degree All edges of a star graph involves the center. Therefore, the center’s indegree = len(edges). Time: , space: . Overlapping vertex Any pair of edges must include the center. So, the center is the overlap between first two edges. Time: , space: . Or,
-
LeetCode 997: Find the Town Judge
link A town judge lacks even self-trust. So, in the trust graph, the town judge looks like a sink: in-degree = n-1 and out-degree = 0. And, there must be exactly one such sink vertex. Time: , space: . More concisely, we can define trustworthiness of a person as (indegree-outdegree). Then, a person with trustworthiness…
-
Subscribe
Subscribed
Already have a WordPress.com account? Log in now.
unreasonably effective 