chocoluffy

// compared to normal dp problem, each case is associated with all prev subproblems! thus need to cache the result.
// following is the dynamic programming version.
for(int i = 0; i < s.size(); i++) {
  vector<string> res;
  for(int j = 0; j < size(); j++) {
    if (dp[j].size() > 0 && dict.find(s.substring(j+1, i)) != dict.cend()) {
      vector<string> curr_list = merge(dp[j], s.substring(j+1, i));
      res.insert(res.end(), curr_list.start(), curr_list.end());
    }
  }

chocoluffy

// [1] know what a normal DFS is when traversing in matrix;
// [2] know how to extend from a normal visited table(a dp table) to hold value for more complex usage. such as holding the maximum value seen so far.

// * [3] another creative solution is to convert the question into finding, the length of longest topological order.

// c++ version:
struct entry {
  int x;
  int y;
}

chocoluffy

// a bst, each node has a parent field. show a in-order traversal of that bst. space complexity O(1). only require one prev pointer.
void in_order_traversal(node* root) {
  node* curr = root, prev;
  while(curr) {
    if (!curr) { // if reach nullptr;
      prev = curr;
      curr = curr->parent;
    }
    else {
      if (curr->left && prev != curr->left) {

chocoluffy

// given a sorted array, build a BST from array of minimum possible height.
node* build_helper(vector<int> array, int start, int end) {
  if (start >= end) {
    node* leave = new Node(array[end], nullptr, nullptr);
    return leave;
  }
  int middle = start + (end - start) / 2;
  node* left_sub = build_helper(array, start, middle);
  node* right_sub = build_helper(array, middle+1, end);
  node* curr = new Node(array[middle], left_sub, right_sub);

chocoluffy

// a O(1) space complexity method for traversing binary tree, but may need modify the tree, thus not thread safe.
void in_order_traversal(node* root) {
  node* curr = root, last;
  while(curr) {
    if (!curr->left) {
      cout << curr->val << endl; // print current node;
      last = curr;
      curr = curr->right;
    } 
    else { 

chocoluffy

bool if_bst(tree* curr) {
  if(!curr) return true;
  // find the rightmost node from the left sub tree;
  tree* left_max= curr->left;
  while(left_max) left_max = left_max->right; // (!left_max || curr->val > left_max->val);
  tree* right_min = curr->right;
  while(right_min) right_min = right_min->left;
  return (!left_max || curr->val > left_max->val) && (!right_min || curr->val < right_min->val) && if_bst(curr->left) && if_bst(curr->right);
}

chocoluffy

// my solution. iterative method. a better solution is recursively build tree by finding range of left and right sub tree.

b_tree* reconstruction(vector<char> &in_order, vector<char> &pre_order) {
  b_tree* root = create_node(pre_order[0]);
  for (int i = 0; i < pre_order.size() - 1; i++) {
    b_tree* curr = root, prev;
    for (int j = 0 ; j < i; j++) {
      prev = curr;
      bool at_left = true;
      if (if_at_left(pre_order[j], pre_order[i], in_order)) { // j is at left to i, insert to curr->left;

chocoluffy

// 很好的参考，对于prev, curr和next的使用。特别是在iterative的方法里。
// trick: 以及很多时候corner case都是根据normal case的nullptr的情况来定义的。

struct b_tree {
  int data;
  b_tree* left;
  b_tree* right;
  b_tree* parent;
}

chocoluffy

// post-order traversal of a binary tree: left subtree, root, right subtree.

struct b_tree {
  int data;
  b_tree* left;
  b_tree* right;
}

void traversal(b_tree* n) {
  if(!n->left && !n->right) {

chocoluffy

// when refer to property using pointer, use `->`, when directly access object's property, use `.`
// this method uses relatively more stack space, can use less space by:
// use curr pointer to go leftest at first, then only expand during `pop()` and print it out.

struct bst_node {
  int data;
  bst_node* left;
  bst_node* right;
}