110
我的思考過程
因為面試的時候，不一定都能很快地想出答案，所以平常訓練的時候就要培養把解題思路說出來的習慣，這個習慣如果養成，不管面對什麼問題，都比較不容易卡死。不過在面試的時候，沒辦法把思路像現在這樣詳細地寫下來，那就只能在白板上列出思考過程中的重點，如果卡住了，就可以從某個重點重新思考。不過重點式思考其實是一種跳躍的思考，在面對較難解的問題的時候，跳躍式思考往往容易讓人卡死，所以接下來這一題，還是先用鉅細靡遺的方式來做，等到已經相當熟悉連續不間斷的思考之後，再來進階，磨練跳躍式思考的能力。
這題是Balanced Binary Tree，首先要把題目看清楚，一開始描述的是有一棵binary tree，要判斷它是不是height-balanced。基本上，看到這裡，只有個大概的感覺，知道大概是要判斷binary tree中，每個節點兩邊的subtree的高度不能差太多，不過差多少算差太多? 還是這種樹是有標準定義的? 我們還是先繼續往下看，如果題目沒有描述，就可以問面試官。
果然題目有解釋，這題要考慮的balanced是指高度不能差超過1，所以只要差到2就不行。
好，假設目前還沒有想法要怎麼實作出這題，那就從題目重新下手，只要把題目完全看透徹，從題目中去感受各種細節，就可以慢慢地把解法生出來，目前先求把解法生出來，程式碼的優化、或是解題速度的優化都是比較後期才該做的事。
從直覺上感覺，最笨的方法就是走過每一個節點，如果不是leaf，就計算兩邊subtree的高度；如果是leaf，就直接跳過。欸不過這邊就有一個問題，印象中以前有上過兩種binary tree的實作方法，根據二元樹實作方法的不同，其資料結構就會不同(例如可能是一個大小跟層數直接相關的陣列、或是用linked list來連接自己定義的節點struct)，我們要寫的程式碼就會不同。不過這邊題目也已經給好資料結構的定義，樹就是TreeNode* root，然後TreeNode的定義是
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
好，回到一開始的想法，如果要走過每一個節點，感覺是可以，只是這樣未免也太慢，感覺怪怪的，應該可以再想一下怎麼做比較合理。(這邊感覺有引出一個重要的技巧，就是不管解法怎麼樣，都先想出一個最笨的解法，然後就寫下來，至少問題是可以被解決，而不是好像想不到夠好的解法就放棄)。
再稍微觀察一下題目，裡面有特別強調 every node，他的意義是每個node往下展開都是一個balanced binary tree，噢噢!所以這就有一點遞迴的fu了，題目的input是root node，就從root node的左跟右分別呼叫一個計算高度的函式，如果這兩個的高度差超過1，那就回傳unbalanced，那如果左跟右沒有差超過1，就回傳左右兩顆子樹中，比較高的那一棵的高度再+1，就可以提供這棵node的parent知道這個node下面的subtree的高度。
要寫出對的程式碼，首先要把程式的運作邏輯想透徹，上面已經得到初步的想法，接下來要把程式的邏輯寫得更完整，順便考慮boundary case，如果去面試的時候也可以列在白板上(不過不知道白板有多大)，可以幫助自己釐清程式的邏輯:
- 如果 tree 是空的，那他就是balanced
- 如果 tree 不是空的，那就分別計算兩邊的 subtree 的高度
- 計算subtree高度時，只要發現是有任一棵subtree是unbalanced，就回傳-1；如果兩棵subtree的高度差超過1，也回傳-1；如果subtree不存在，就回傳0；如果兩棵subtree的高度不差超過1，就回傳比較高的那一棵的高度+1
好，根據以上的邏輯，寫程式就變得很簡單了，這邊就直接實作:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isBalanced(TreeNode* root) {
if(root == NULL)
return true;
if(height(root)==-1)
return false;
return true;
}
int height(TreeNode* node)
{
if(node == NULL)
return 0;
TreeNode* leftChild = node->left;
int leftH = height(leftChild);
if(leftH == -1)
return -1;
TreeNode* rightChild = node->right;
int rightH = height(rightChild);
if(rightH == -1)
return -1;
if(abs(rightH-leftH)>1)
return -1;
return max(leftH, rightH)+1;
}
};
雖然解出這題了，不過很明顯可以看出思考的過程還不夠精煉，這部分就是如果要去面試，得額外花心思加強的點，不過我想演示的是，透過慢慢地觀察題目、從每個想得不夠清楚的點往下深入，就會慢慢看出一些端倪，接著再將這些蛛絲馬跡串起來，然後想得更完整，就可以寫出邏輯，一旦把邏輯寫出來，剩下就只是寫成程式碼。其實難的點還是在於怎麼不卡關地把程式的邏輯想出來。
延伸的思考
- Binary tree之所以叫做binary，是因為每個節點只能有兩個小孩，就好像在中國一樣，只是變成二胎化政策。
- Binary Tree到底可以做什麼? 直覺上會想到可以用來做排序和搜索，因為不管要找的東西在樹的哪一邊，都不會找太久的時間。不過在實際的應用上有可能建這麼大的樹嗎? (有空可以看看相關的應用)
解法的優化
public class Solution {
public boolean isBalanced(TreeNode root) {
return findDepth(root) == -1 ? false: true;
}
int findDepth(TreeNode root){
if(root == null) return 0;
int left = findDepth(root.left);
if(left == -1) return -1;
int right = findDepth(root.right);
if(right == -1) return -1;
if(Math.abs(left-right) >1) return -1;
return Math.max(left, right)+1;
}
}