今天的題單：

• Validate Binary Search Tree

• Number of Islands

98. Validate Binary Search Tree

Attempt 1: 如果是一個 BST，inorder traversal 的 node value 順序必定是遞增的。時間和空間複雜度分別是都是 O(n)。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        vector<int> vec;
        traverse(root, vec);

        for (int i = 1; i < vec.size(); i++) {
            if (vec[i] <= vec[i-1]) return false;
        }
        return true;
        
    }

    void traverse(TreeNode* node, vector<int>& vec) {
        if (node == NULL) return;
        
        traverse(node->left, vec);
      
        vec.push_back(node->val);
      
        traverse(node->right, vec);
    }
};

Attempt 2: 用遞迴的方式檢查 subtree 是否也是一個 BST。

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        
        return checkBST(root, LONG_MIN,LONG_MAX);
    }

    bool checkBST(TreeNode* node, long min_boundary, long max_boundary) {
        if (node == nullptr) 
            return true;

        if (node->val <= min_boundary || node->val >= max_boundary)
            return false;

        return checkBST(node->left, min_boundary, node->val) && checkBST(node->right, node->val, max_boundary);
    }
};

200. Number of Islands

計算地圖（grid）上的島嶼數量。”1” 代表陸地，”0” 代表水。

Example:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

思路：如果陸地是屬於同一個島嶼，其中所有的 1 必定是相連的（上下左右）。先辨識出所有的陸地，再用 DFS 去辨識同一個島嶼的所有陸地。DFS 每次結束都是辨識出一個島嶼。只要計算 DFS 做了幾次就表示有幾個島嶼。

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        queue<pair<int, int>> q;  // coordinates
        vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), false));
        int num = 0;

        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[i].size(); j++) {
                if (grid[i][j] == '1')
                    q.push({i, j});
            }
        }

        while (!q.empty()) {
            pair<int, int> loc = q.front();
            if (!visited[loc.first][loc.second]) {
                // DFS
                dfs(loc.first, loc.second, grid, visited);
                
                num += 1;
            }
            q.pop();
        }

        return num;
    }

    void dfs(int i, int j, vector<vector<char>>& grid, vector<vector<bool>>& visited) {
        // check boundary
        if (i < 0 || i >= grid.size() || j < 0 || j >= grid[i].size())
            return;
        if (visited[i][j] || grid[i][j] == '0')
            return;
        
        visited[i][j] = true;

        dfs(i+1, j, grid, visited);
        dfs(i-1, j, grid, visited);
        dfs(i, j+1, grid, visited);
        dfs(i, j-1, grid, visited);
    }
};