Some topics from either oj.leetcode.com or hackerrank:

Palindrome

• Palindrome Number
  Is a number palindrome?
  Solution: reverse the integer and see if they equal. Pay attention to the sign
  Big-O: 0 space n time (n is the length of number)
• Palindrome Partition I
  Find all possible ways to partition a string into palindrome substrings
  Solution: DP
  Big-O: n^2 space 2^n time (n is the length of string)
• Palindrome Partition II
  Find the minimum number of cuts to partition a string into palindrome substrings
  Solution: Double DP. If use the previous problem, too much space and time.
  Find P[i][j] s.t. P[i][j] is true if s[i:j] is palindrome. D[i] is the mincut
  of s[i:].
  Big-O: n^2 space n^2 time (n is the length of string)
• Palindrome Index
  Find the index in the string which if removed, makes the string palindrome
  Solution: TODO
• Longest Palindrome Substring
  Solution: We can use the DP in “Pal Part II”, which will have O(n^2) big-O. Or we can use manacher’s algorithm in O(n).

---

Binary Tree

• Preorder Traversal
  Solution: Trivial
• Postorder Traversal
  Solution: Trivial
• Inorder Traversal
  Solution: Trivial
• Binary Tree Maximum Sum
  Solution: This problem has a lot of edge cases, and the “path” is not so well-defined in the problem.
  This problem seems to be a DP problem at the first sight, but if you think about it, you can expand in
  two directions at the root, but not at children of root, which is not a “path”. I used a hash table
  to store each node’s single path sum, defined as the max sum reached by going either to the left
  or to the right, but not both. And traverse the tree to compute each node’s maxPathSum.
  Big-O: n space nlogn time
• Flatten Binary Tree to Linked List
  Solution: Use a queue. Brute force solution.
  Big-O: n space n time
• Minimum depth of tree
  Find the minimum distance from root to a leaf node
  Solution: this problem is not complicated, but not as trivial as it first appears. Consider (1, #, 2) as
  an edge case.
  Big-O: 1 space d work
• Balanced Binary Tree
  Solution: Trivial

  TODO: AVL Tree

• Sorted Array to Binary Tree
  Solution: similar to binary search
  Big-O: n space n time
• Sorted list to Binary Tree
  Solution: Use the above program
  Big-O: n space n time
• Maximum Depth of Binary Tree
  Solution: Trivial
• Level order Traversal
  Solution: Create a hash table of
  Big-O: n time n space
• Level order Traversal II
  Solution: Similar to the above problem.
• Zigzag level order traversal
  Solution: Similar to the above
• Same Tree
  Solution: Trivial