Multi-end BFS

BFS and DFS are usually used in searching problem. But for a specific kind of problem, we should use a optimized BFS, Multi-end BFS to guarantee the efficiency of the solution. This kind of problems has the following features: There are many entrances in the searching space. We want the minimum or the maximum solutions.

Tree Serialization

Serialization means transforming tree structure to a linear structure to store it. Generally, traversal is used to implement serialization. So, what kinds of traversal could be used to implement serialization? We mainly focus on binary tree in this article. At the end of the article we will discuss a little about N-ary tree. 1 Serialization

Tree Traversal

Generally, tree traversal can be specified as inorder traversal (only for binary tree) , preorder traversal, postorder traversal and level order traversal. Level order traversal can be easily implemented with a queue. But other three traversals could be implemented recursively, iteratively with O(n) space and even iteratively with O(1) space. We focus on binary tree

Union-Find

Union-Find is a data structure to check a cycle in the graph. Every node in the graph has its own parent. So we need a parent array to should each node’s parent. Set the initial parent of each node to itself. And we need a rank array to show the height of the tree of

Task Scheduler

Description LeetCode 621 Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks.Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle. However, there is

Stable Matching

Problem Input: Two set of equal size + the preferences of each element Goal: Find a perfect stable matching We can formulating the problem as a stable marriage problem. Given \(n\) men and \(n\) women, find a stable matching. Each man lists women in order of preference from best to worst. So as each woman.

Word Ladder

Description LeetCode 127 Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that: Only one letter can be changed at a time. Each transformed word must exist in the word list. Note that beginWord is not a transformed word. Note: Return 0 if there is no such transformation sequence. All

Populating Next Right Pointers in Each Node II

Description LeetCode 117 Given a binary tree struct TreeLinkNode { TreeLinkNode *left; TreeLinkNode *right; TreeLinkNode *next; } Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. Initially, all next pointers are set to NULL. Note: You may only use constant

Binary Tree Maximum Path Sum

Description LeetCode 124 Given a non-empty binary tree, find the maximum path sum. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root. Example 1: Input:

Distinct Subsequences

Description LeetCode 115 Given a string S and a string T, count the number of distinct subsequences of S which equals T. A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ACE” is a subsequence of “ABCDE” while “AEC” is not).