【ING】dfs总结

https://leetcode.com/tag/depth-first-search/

https://leetcode.com/problems/longest-increasing-path-in-a-matrix/

class Solution {
    int dfs(vector<vector<int>>& matrix, vector<vector<int> > & visited, int x, int y) {
        if(visited[x][y] != -1)
            return visited[x][y];
        int res = 1;
        //left
        if(y > 0 && matrix[x][y-1] > matrix[x][y])
            res = max(res, dfs(matrix, visited, x, y-1) + 1) ;
        //right
        if(y < matrix[0].size() - 1 && matrix[x][y+1] > matrix[x][y])
            res = max(res, dfs(matrix, visited, x, y+1) + 1);
        //up
        if(x > 0 && matrix[x-1][y] > matrix[x][y])
            res = max(res, dfs(matrix, visited, x-1, y) + 1);
        //down
        if(x < matrix.size() - 1 && matrix[x+1][y] > matrix[x][y])
            res = max(res, dfs(matrix, visited, x+1, y) + 1);
        visited[x][y] = res;
        return res;
    }
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int m = matrix.size();
        if(m == 0) return 0;
        int n = matrix[0].size();
        if(n == 0) return 0;
        
        vector<vector<int> > visited(m,vector<int>(n, -1));
        
        int res = 0;
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                res = max(res, dfs(matrix, visited, i, j));
        return res;
    }
};

https://leetcode.com/problems/maximum-depth-of-binary-tree/
递归版本：

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == NULL) return 0;
        return max(maxDepth(root->left),maxDepth(root->right)) + 1;
    }
};

非递归版本(bfs)：

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == NULL) return 0;
        queue<TreeNode *> nodeQueue;
        int res = 0;
        nodeQueue.push(root);
        while(!nodeQueue.empty()) {
            res++;
            int tmpsize= nodeQueue.size();
            for(int i = 0; i < tmpsize; i++) {
                TreeNode * temp = nodeQueue.front();
                nodeQueue.pop();
                //cout<<"res="<<res<<"; node="<<temp->val<<endl;
                if(temp->left != NULL)  nodeQueue.push(temp->left);
                if(temp->right != NULL) nodeQueue.push(temp->right);
            }
        }
        return res;
    }
};

same tree
https://leetcode.com/problems/same-tree/

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p == NULL && q == NULL) return true;
        if(p == NULL || q == NULL) return false;
        if(p->val != q->val) return false;
        return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
    }
};

https://leetcode.com/problems/balanced-binary-tree/
这个方法感觉不好，在不停的进行重复的遍历：

class Solution {
    int getHeight(TreeNode * root) {
        if(root == NULL) return 0;
        return max(getHeight(root->left),getHeight(root->right)) + 1;
    }
public:
    bool isBalanced(TreeNode* root) {
        if(root == NULL) return true;
        int l = getHeight(root->left);
        int r = getHeight(root->right);
        if(abs(l-r) <= 1 && isBalanced(root->left) && isBalanced(root->right)) return true;
        return false;
    }
};

https://leetcode.com/discuss/22898/the-bottom-up-o-n-solution-would-be-better

class solution {
public:
int dfsHeight (TreeNode *root) {
        if (root == NULL) return 0;

        int leftHeight = dfsHeight (root -> left);
        if (leftHeight == -1) return -1;
        int rightHeight = dfsHeight (root -> right);
        if (rightHeight == -1) return -1;

        if (abs(leftHeight - rightHeight) > 1)  return -1;
        return max (leftHeight, rightHeight) + 1;
    }
    bool isBalanced(TreeNode *root) {
        return dfsHeight (root) != -1;
    }
};

https://leetcode.com/problems/number-of-islands/
dfs, bfs, union find

dfs：

class Solution {
    void dfs(vector<vector<char>> &grid, vector<vector<bool>> &visited, int x, int y) {
        if(visited[x][y]) 
            return;
        visited[x][y] = true;
        //up
        if(x > 0 && grid[x-1][y] == '1')
            dfs(grid, visited, x-1, y);
        //down
        if(x < grid.size() - 1 && grid[x+1][y] == '1')
            dfs(grid, visited, x+1, y);
        //left
        if(y > 0 && grid[x][y-1] == '1')
            dfs(grid, visited, x, y-1);
        //right
        if(y < grid[0].size() - 1 && grid[x][y+1] == '1')
            dfs(grid, visited, x, y+1);
    }
public:
    int numIslands(vector<vector<char>> &grid) {
        int m = grid.size();
        if(m == 0) return 0;
        int n = grid[0].size();
        if(n == 0) return 0;
        vector<vector<bool> > visited(m,vector<bool>(n,false));
        
        int num = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == '1' && !visited[i][j]) {
                    dfs(grid, visited, i, j);
                    num++;
                }
            }
        }
        return num;
    }
};

bfs:

class Solution {
    void bfs(vector<vector<char>> &grid, vector<vector<bool>> &visited, int x, int y) {
        queue<pair<int,int>> q;
        q.push(make_pair(x,y));
        visited[x][y] = true;
        while(!q.empty()) {
            auto i = q.front();
            q.pop();
            x = i.first;
            y = i.second;
            if(x > 0 && grid[x-1][y] == '1' && visited[x-1][y] == false) {
                q.push(make_pair(x-1,y));
                visited[x-1][y] = true;
            }
            if(x < grid.size() - 1 && grid[x+1][y] == '1' && visited[x+1][y] == false) {
                q.push(make_pair(x+1,y));
                visited[x+1][y] = true;
            }
            if(y > 0 && grid[x][y-1] == '1' && visited[x][y-1] == false) {
                q.push(make_pair(x,y-1));
                visited[x][y-1] = true;
            }
            if(y < grid[0].size() - 1 && grid[x][y+1] == '1' && visited[x][y+1] == false) {
                q.push(make_pair(x,y+1));
                visited[x][y+1] = true;
            }
        }
    }
public:
    int numIslands(vector<vector<char>> &grid) {
        int m = grid.size();
        if(m == 0) return 0;
        int n = grid[0].size();
        if(n == 0) return 0;
        vector<vector<bool> > visited(m,vector<bool>(n,false));
        
        int num = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == '1' && !visited[i][j]) {
                    bfs(grid, visited, i, j);
                    num++;
                }
            }
        }
        return num;
    }
};

union-find:

class Solution {
    vector<int> roots;
    int findRoot(int idx) {
        while(roots[idx] != idx)
            idx = roots[idx];
        return idx;
    }
public:
    int numIslands(vector<vector<char>> &grid) {
        int m = grid.size();
        if(m == 0) return 0;
        int n = grid[0].size();
        if(n == 0) return 0;
        
        roots.resize(m * n, -1);
        vector<vector<int>> dirs = {{-1,0},{1,0},{0,-1},{0,1}};
        
        int num = 0;
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                if(grid[i][j] == '1') {
                    roots[i * n + j] = i * n + j;
                    num++;
                }
        cout<<"num="<<num<<endl;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == '0') 
                    continue;
                int id_old = i * n + j;
                for (auto & d:dirs) {
                    if(i + d[0] < 0 || i + d[0] >= m || j + d[1] < 0 || j + d[1] >= n)
                        continue;
                    if(grid[i + d[0]][j + d[1]] == '0')
                        continue;
                    int id_new = (i + d[0]) * n + (j + d[1]);
                    int root_new = findRoot(id_new);
                    int root_old = findRoot(id_old);
                    if(root_new != root_old) {
                        roots[root_new] = root_old;
                        num--;
                    }
                }
            }
        }
        return num;
    }
};

number of island ii:
https://leetcode.com/problems/number-of-islands-ii/

class Solution {
    vector<int> parents;
    int num;
    void uf(int old_id, int new_id) {
        int old_root = find(old_id);
        int new_root = find(new_id);
        if(old_root != new_root) {
            parents[old_root] = new_root;
            num--;
        }
    }
    
    int find(int id) {
        while(parents[id] != id)
            id = parents[id];
        return id;
    }
public:
    vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
        parents.resize(m * n, -1);
        vector<int> res;
        num = 0;
        for(auto &i : positions) {
            int x = i.first;
            int y = i.second;
            int id = x * n + y;
            parents[id] = id;
            num++;
            if(x > 0 && parents[(x - 1) * n + y] != -1)
                uf(id, (x - 1) * n + y);
            if(x < m - 1 && parents[(x + 1) * n + y] != -1)
                uf(id, (x + 1) * n + y);
            if(y > 0 && parents[x * n + (y - 1)] != -1)
                uf(id, x * n + (y - 1));
            if(y < n - 1 && parents[x * n + (y + 1)] != -1)
                uf(id, x * n + (y + 1));
            res.push_back(num);
        }
        return res;
    }
};