Category: tree_dfs
-
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.
-
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…
unreasonably effective 