跳转至

Traversal


  • complement: recursion

Graph

Binary Tree

  • Preorder Traversal

  • Inorder Traversal

    • 二叉搜索树的中序遍历为 递增序列
  • Postorder Traversal

    C++
    vector<int> *res;
    void dfs(TreeNode* node) {
        if(node->left != nullptr) dfs(node->left);
        if(node->right != nullptr) dfs(node->right);
        res->push_back(node->val);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        res = new vector<int>();
        if(root != nullptr) dfs(root);
        return *res;
    }
    

  • complement: iteration / circulation

Binary Tree

  • Level-order Traversal
    C++
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ret;
        if(root == nullptr) return ret;
    
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
            int sz = q.size();
            ret.push_back(vector<int>());
            for(int i=0; i<sz; i++) {
                auto node = q.front(); q.pop();
                ret.back().push_back(node->val);
                if(node->left != nullptr) q.push(node->left);
                if(node->right != nullptr) q.push(node->right);
            }
        }
    
        return ret;
    }
    
  • Dijkstra Algorithm

LeetCode

  • leetcode 200: 岛屿数量
    C++
    int nr = 0;
    int nc = 0;
    const int dx[4] = {0, 0, -1, 1};
    const int dy[4] = {-1, 1, 0, 0};
    
    void dfs(vector<vector<char>>& grid, int r, int c) {
        grid[r][c] = '0';
    
        if(r-1>=0 && grid[r-1][c] == '1') dfs(grid, r-1, c);
        if(r+1<nr && grid[r+1][c] == '1') dfs(grid, r+1, c);
        if(c-1>=0 && grid[r][c-1] == '1') dfs(grid, r, c-1);
        if(c+1<nc && grid[r][c+1] == '1') dfs(grid, r, c+1);
    }
    
    void bfs(vector<vector<char>>& grid, int r, int c) {
        queue<std::pair<int,int>> que;
        que.push({r,c});
        grid[r][c] = '0';
    
        while(!que.empty()) {
            auto rc = que.front();
            que.pop();
            for(int i=0; i<4; i++) {
                int y = rc.first + dy[i];
                int x = rc.second + dx[i];
                if(x>=0 && x<nc && y>=0 && y<nr && grid[y][x]=='1') {
                    que.push({y, x});
                    grid[y][x] = '0';
                }
            }
        }
    }
    
    int numIslands(vector<vector<char>>& grid) {
        nr = grid.size();
        if(nr == 0) return nr;
        nc = grid[0].size();
    
        int num = 0;
        for(int y=0; y<nr; y++) {
            for(int x=0; x<nc; x++) {
                if(grid[y][x] == '1') {
                    num++;
                    bfs(grid, y, x);
                }
            }
        }
        return num;
    }