寫 leetcode 小感想

最近偶而會找一點時間寫 leetcode 的題目
目前剛剛清空 easy 等級，正在挑戰 medium
常常看到別人提供的解答，會發現為什麼 code 可以這麼短


初步的心得是很多特定的題目格式都有一些固定的 pattern
如果照著某些 pattern 去寫的話，程式的邏輯就會變很清楚
要改動就很容易，寫過一次 code 就能很快解開所有類似的題目
反之自己硬爆出來東西就會有一堆 adhoc 的東西，很難改
這邊把我目前遇到的部份記錄下來

Tree Traversal

舉 balanced binary tree 為例
題目想問是否所有的 node 兩邊的高度差是不是 <= 1

recursive 的作法大約是

1. 檢查左邊是不是 balanced binary tree，順便取得左邊的高度 l（回傳）
2. 檢查右邊邊是不是 balanced binary tree，順便取得右邊的高度 r（回傳）
3. 檢查兩邊的 abs(l-r) <= 1，並且回傳 max(l,r)+1 為自己的高度

但是我比較喜歡自己用 stack 維護
因此我試著用 state, case 模擬 recursive
經過測試這個作法可以很快的改動，把所有 tree-based easy 的題目寫完
首先我們會宣告 state 應該要有的資訊
最少需要 current node 跟已經 traverse 的方向 (state)
以及需要函數的 return value

struct StackInfo {
 TreeNode *cur;
 HasDoneDirection state;
 int left_height;
};
int returned_height;
stack<stackinfo> traverse_stack;

下面就是 traversal 的部份
想要把 recursive 到下級的時候就用 break + push + change state
並且把需要的變數存起來
想要 return 的時候就用 break + pop，並且寫入 return value
只要在需要的地方把 return value 接收下來就行了
我覺得把 switch case 去掉之後其實就跟 recursive 的邏輯一樣了
為了清晰這個 code 把很多地方拔掉了，例如一些變數的定義跟 null 的檢查

traverse_stack.push({root, NEW_NODE, 0});
while (traverse_stack.size() != 0) {
 switch (state) {
  case NEW_NODE: {
   traverse_stack.push({cur->left, NEW_NODE});
   state = DONE_LEFT;
   break;
  }
  case DONE_LEFT: {
   left_height = returned_height;
   traverse_stack.push({cur->right, NEW_NODE});
   state = DONE_RIGHT;
   break;
  }
  case DONE_RIGHT: {
   int right_height = returned_height;
   if (abs(left_height - right_height) > 1) {
    return false;
   }
   returned_height = max(left_height, right_height) + 1;
   traverse_stack.pop();
  }
 }
}
return true;

之後繼續寫一寫看看還有沒有遇到有趣的 case