今天的題單：

• Flood Fill

• Lowest Common Ancestor of a Binary Search Tree

733. Flood Fill

查 wiki 後看到圖就懂了，簡單來說就是從 start pixel 開始對相鄰相同顏色的區域塗色。這題看4 direction，也就是會檢查 pixel 的上下左右相連的四格。

這題用 DFS 做，注意一下邊界條件檢查即可。

class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {

        // if the starting color and the target color are same, then no changes are made
        if (image[sr][sc] == color) {
            return image;
        }
        
        // DFS
        dfs(image, sr, sc, image[sr][sc], color);

        return image;
    }

    void dfs(vector<vector<int>>& image, int sr, int sc, int start_color, int new_color) {
        // boundary checking
        if (sr < 0 || sr >= image.size() || sc < 0 || sc > image[0].size()) {
            return;
        }
        if (image[sr][sc] == start_color) {
            image[sr][sc] = new_color;
            
            // Explore the 4 direction 
            dfs(image, sr - 1, sc, start_color, new_color);
            dfs(image, sr + 1, sc, start_color, new_color);
            dfs(image, sr, sc - 1, start_color, new_color);
            dfs(image, sr, sc + 1, start_color, new_color);
        }
    }
};

235. Lowest Common Ancestor of a Binary Search Tree

思路：標記找到 node 的兩條路線，比對經過的 node，找到最底層被標記過兩次的 node，它就是 LCA。

/**
 * 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:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        vector<TreeNode*> trace_p;
        vector<TreeNode*> trace_q;

        find_node(root, p, trace_p);
        find_node(root, q, trace_q);

        int len = min(trace_p.size(), trace_q.size());

        TreeNode* lca = nullptr;

        for (int i = 0; i < len; i++) {
            if (trace_p[i] == trace_q[i])
                lca = trace_p[i];
        }

        return lca;
    }

    void find_node(TreeNode* root, TreeNode* node, vector<TreeNode*>& trace) {
        if (root == node) {
            trace.push_back(node);
            return;
        }

        trace.push_back(root);
        
        int val = node->val;

        if (val < root->val) { // go left
            find_node(root->left, node, trace);
        } else if (val > root->val) { // go right
            find_node(root->right, node, trace);
        }
    }
};