Trees

814. Binary tree pruning

814. Binary tree pruning

// https://leetcode-cn.com/problems/binary-tree-pruning/
// 814. Binary tree pruning

2. If the left and right nodes exist, it proves that the tree has the value of existence (there is 1). Therefore, the judgment conditions are 3 * 2.1, which are whether the left and right nodes exist and whether the current root node is 1 respectively, and the union can be taken */
var pruneTree = function (root) {
    if(! root)return null
    root.left = pruneTree(root.left)
    root.right = pruneTree(root.right)
    if (root.val || root.left || root.right) return root
    return null
}
Copy the code

91 Algorithm – search

695. The largest area of the island

695. The largest area of the island

Analysis of the

  1. This problem is to see the solution to understand after doing
  2. Each DFS takes the values around them. In fact, DFS here is more like DP state, and their state is maintained by four DFS around Shen
  3. Since other DPS may have already taken the value of one of the islands, to ensure no duplication, set the value of the islands traversed to 0, so that any value can be represented by its four dp states

The border

  1. The edges don’t have 4 directions, so they need to have a layer of virtual ocean — everything beyond is 0
  2. If it is the location of the sea, we do not need to consider, just skip it
// https://leetcode-cn.com/problems/max-area-of-island/
// 695. The largest area of the island

/** * use depth-first traversal + quadrangle to solve this problem * @ analysis * 1. Islands traversed once are marked as already traversed, i.e. 0, to prevent repeated traversal
var maxAreaOfIsland = function (grid) {
    let max =0
    const row = grid.length
    const column = grid[0].length
    const dfs = (i, j) = > {
        // If it traverses the ocean, or if it is out of range, it is treated as ocean
        if (i >= row || i < 0 || j >= column || j < 0) {
            return 0
        }
        if(! grid[i][j])return 0
        // As long as traversal, directly set to 0, do not repeat walk
        grid[i][j] = 0
        // A normal value
        return 1 + dfs(i - 1, j) + dfs(i + 1, j) + dfs(i, j - 1) + dfs(i, j + 1)}for (let i = 0; i < row; i++) {
        for (let j = 0; j < column; j++) {
            max =  Math.max(dfs(i, j),max)
        }
    }
    return max
};
Copy the code