My code can be viewed in my github: Proverbs Github.
The following difficulty is defined by myself.

all-paths-from-source-to-target(easy)

DFS and keep track of current path.

  • Time complexity: O(n).
  • Space complexity: O(n).

convert-sorted-list-to-binary-search-tree(medium)

The same as building BST from sorted array. And the only difference is we should traverse the whole linked list to get its length is each round of DFS. So, the time complexity will be O(nlogn) rather than O(n).
Another smarter O(n) solution is using in-order traversal: Link, which is to keep track of current node pointer and build the tree from left to right using recursion of in-order traversal.

  • Time complexity: O(nlogn).
  • Space complexity: O(n).

find-duplicate-subtrees(medium)

Tree serialization.

  • Time complexity: O(n^2) for the worst case that the tree is a linked list.
  • Space complexity: O(n^2).

find-k-pairs-with-smallest-sums(hard)

Consider a 2D table from nums1 x nums2. Then, you will find some rules and figure out the solution.

2D table.

  • Time complexity: O(klogk).
  • Space complexity: O(k).

maximum-binary-tree(hard)

Build “BST”. To solve the queries of the maximum value of intervals, a better way is segment tree, though I used brute force.
However, I think brute force and segment solutions are both O(nlogn).
A quite brilliant resolution is based on the finding that the parent of a node = min(nearest max to the left, nearest max to the right), which can be seen at Link.

  • Time complexity: O(nlogn).
  • Space complexity: O(n).

maximum-vacation-days(medium)

DP.
dp[i][j]: max vacation if staying at place i in the j-th week.

  • Time complexity: O(n^2k)
  • Space complexity: O(nk).

one-edit-distance(easy)

Because we can only use the operations once, we can just use DFS.

  • Time complexity: O(n).
  • Space complexity: O(n).

shortest-path-visiting-all-nodes(medium)

The simplest state compressed DP.
dp[x][state]: max vacation days if cities you have been to are state, and you are current staying at x.
A trick is how to handle the problem that you can go to a cities many times. My solution is to add an additional loop to modify dp array: modify n times for dp[point][state], because dp[p1][state] can be modified by dp[p2][state].

  • Time complexity: O(n^3*2^n).
  • Space complexity: O(n*2^n).

shortest-word-distance(easy)

Find the nearest word2 left or right to each word1.

  • Time complexity: O(n).
  • Space complexity: O(1).

valid-triangle-number(medium)

Sort + two pointers, which is similar to 3sum.

  • Time complexity: O(n^2).
  • Space complexity: O(n).