今天討論 一題 Tree 與 一題 Graph 圖。

543. Diameter of Binary Tree (easy)

題目說明: 給根節點，求直徑。直徑是指樹中任兩個節點之間最長路徑的長度。

輸入範例:

		1
	   / \
	  2   3
	 / \
	4   5

輸出為3

我第一直覺的解題是求 root 的左右子樹的高度，然後相加就是答案。
(3-1-2-4)

因此寫成 (錯誤程式碼)

class Solution {

public:
    int height(TreeNode *root) {
        if(!root) return 0;
        return max((height(root->left)+1), height(root->right)+1);
    }

    int diameterOfBinaryTree(TreeNode* root) {
        int sum = 0;
        if (root->left) sum += height(root->left);
        if (root->right) sum+= height(root->right);
        return sum;
    }

};

但 leetcode 題目上就有提示到: 直徑的路徑"可能會也可能不會"通過根節點!
反例如:

		1 
	   /  
	   2 
      / \ 
     3  4
    /
   5

在這個例子中，直徑實際上是 (4-2-3-5)，不經過根節點。因此，我們需要在每個節點遞迴計算高度的同時，檢查該節點是否可能成為直徑中的中間節點

class Solution {
public:
    int maxDiameter = 0;
    int height(TreeNode *root) {
        if(!root) return 0;
        int sum = 0;
        int leftHeight = height(root->left);
        int rightHeight = height(root->right);
        maxDiameter = max(maxDiameter, leftHeight+rightHeight);
        return max(leftHeight, rightHeight) + 1;
    }
    int diameterOfBinaryTree(TreeNode* root) {
        height(root);
        return maxDiameter;        
    }
};

785. Is Graph Bipartite? (medium)

題目說明: 這題的目標是檢查一個圖是否是二分圖，即是否可以將圖的節點分成兩個集合，並且確保每條邊的兩個節點分別屬於不同集合。

吳邦一教授講到:

這個題目是二分圖檢測的裸題。
圖論中，所謂點的著色是給每一個點一個顏色編號，必須滿足：相鄰的點必須著不同色。
二分圖就是可以只用二色著色。我們可以用著色的概念來檢測

我的解題思路:
要確保鄰居與自己不同色。因此在做 BFS(也可以做DFS)時，如果鄰居還沒塗色，將為鄰居塗上與自己不同顏色。但凡遍歷過程發現鄰居與自己撞色，那就不是二分圖。

由於不知道圖上是否只有一個連通分量，因此用for loop跑所有的節點當 BFS 的起點，確定每個節點全都都會塗到色。

顏色三種: {0,1,-1}，其中0 代表沒塗色。

class Solution {
public:
    vector<int>colors; // to record node color
    queue<int> qu;
    bool bfs(int root, vector<vector<int>>& graph) {
        colors[root] = 1;
        qu.push(root);
        while(!qu.empty()) {
            int tp = qu.front();
            qu.pop();
            for (int n: graph[tp]) {
                if (colors[n] == colors[tp]) {
                    return false;
                }
                if (colors[n] == 0) {
                    colors[n] = -colors[tp];
                    qu.push(n);
                }
            }
        }
        return true;
    }
    bool isBipartite(vector<vector<int>>& graph) {
        colors = vector<int>(graph.size(), 0);
        for (int i = 0; i < graph.size(); i++) {
            if (colors[i] != 0) continue;
            if (!bfs(i, graph)) return false;
        }
        return true;
    }
};