leetcode深度优先搜索（dfs）

深碍√TFBOYSˉ_ 2022-09-04 09:53 185阅读 0赞

1.  图像渲染

有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在 0 到 65535 之间。

给你一个坐标 (sr, sc) 表示图像渲染开始的像素值（行 ，列）和一个新的颜色值 newColor，让你重新上色这幅图像。

为了完成上色工作，从初始坐标开始，记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为新的颜色值。

最后返回经过上色渲染后的图像。

翻译：给你一个矩阵：

\[\[1,1,1\],

\[1,1,0\],

\[1,0,1\]\]

然后给你一个坐标（1,1）和新数值（2），要求你把坐标及其周围的旧数值变为新数值，即新矩阵为：

\[\[2,2,2\],

\[2,2,0\],

\[2,0,1\]\]

写这种递归调用的搜索函数时，注意递归退出的条件写清。  
本题的退出条件：

class Solution {
        
        public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        
            int a=image[sr][sc];
            if(a!=newColor){
        changes(image,sr,sc,a,newColor);}            
            return image;
        }
        public void changes(int[][] image,int i,int j,int a,int newColor){
        
            if(i<0||i==image.length||j<0||j==image[0].length||image[i][j]!=a){
        //不能出界，image[i][j]!=a指该当前格子已经完成更改。
                return;
            }
            image[i][j]=newColor;
            changes(image,i+1,j,a,newColor);
            changes(image,i-1,j,a,newColor);
            changes(image,i,j+1,a,newColor);
            changes(image,i,j-1,a,newColor);
        }
    }

1.  岛屿的最大面积

给定一个包含了一些 0 和 1 的非空二维数组 grid 。

一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)

与之前写过的走迷宫类似，遍历每个格子，从每个格子开始搜索求出最大值。  
搜索过程中，当前为1时，将该点置为0（防止重复计算），计数并递归计算该点四个方向上的值。

class Solution {
        
    
        public int find(int[][] grid,int i,int j){
        
            if((i>=0)&&(i<grid.length)&&(j>=0)&&(j<grid[0].length)){
        
                
                if(grid[i][j]==1)
                {
        
                    grid[i][j]=0;
                    return 1+find(grid,i+1,j)+find(grid,i-1,j)+find(grid,i,j+1)+find(grid,i,j-1);}
                else{
        
                return 0;
            }
            }
            else{
        
            return 0;
            }
        }
        public int maxAreaOfIsland(int[][] grid) {
        
        int q=0;
        for(int i=0;i<grid.length;i++){
        
            for(int j=0;j<grid[0].length;j++){
        
            q=Math.max(q,find(grid,i,j));
            }
        }
        return q;
        }
    }

1.  合并二叉树

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。  
Tree 1 Tree 2  
1 2  
/ \\ / \\  
3 2 1 3  
/ \\ \\  
5 4 7  
3  
/  
4 5  
/ \\ \\  
5 4 7

递归深搜…

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
        public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        
        if(root1==null){
        
            return root2;//若一个为空，直接计算另一个即可
        }
        if(root2==null){
        
            return root1;//同上
        }
        TreeNode merge=new TreeNode(root1.val+root2.val);//申请个新的，不改变原来的。
        merge.left=mergeTrees(root1.left,root2.left);
        merge.right=mergeTrees(root1.right,root2.right);
        return merge;
        }
    }

1.  填充每个节点的下一个右侧节点指针  
    给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node \{  
int val;  
Node \*left;  
Node \*right;  
Node \*next;  
\}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

你只能使用常量级额外空间。  
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。  
输入：root = \[1,2,3,4,5,6,7\]  
输出：\[1,\#,2,3,\#,4,5,6,7,\#\]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FieXNzd2F0Y2hlcjE_size_16_color_FFFFFF_t_70]观察可知，递归结束条件：值为null（传入的是末端节点的子节点，所以为null结束）。  
一个节点的左子的next指向其右子。  
一个节点的右子的next指向该节点next节点的左子。

/*
    // Definition for a Node.
    class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;
    
        public Node() {}
        
        public Node(int _val) {
            val = _val;
        }
    
        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    };
    */
    
    class Solution {
        
        public Node connect(Node root) {
        
        if(root==null){
        
            return null;
        }
        if(root.left!=null)//因为是完美二叉树，所以若左子不存在，不用判断后续。
        {
        root.left.next=root.right;
        if(root.next!=null){
        
            root.right.next=root.next.left;
        }
        }
        connect(root.left);
        connect(root.right);
        return root;}
    }

1.  填充每个节点的下一个右侧节点指针 II

给定一个二叉树

struct Node \{  
int val;  
Node \*left;  
Node \*right;  
Node \*next;  
\}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。  
与上题区别为不是完美二叉树。  
按照层次遍历的写法，，设置next指针。

/*
    // Definition for a Node.
    class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;
    
        public Node() {}
        
        public Node(int _val) {
            val = _val;
        }
    
        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    };
    */
    
    class Solution {
        
        public Node connect(Node root) {
        
        if(root==null){
        
            return null;
        }
        Queue<Node> queue=new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
        
            int levelsize=queue.size();
            Node pre=null;
            for(int i=0;i<levelsize;i++){
        
                Node node=queue.poll();
                if(pre!=null){
        
                    pre.next=node;
                }
                pre=node;
                if(pre.left!=null){
        
                    queue.add(pre.left);
                }
                if(pre.right!=null){
        
                    queue.add(pre.right);
                }
            }
        }
        return root;
        }
    }

1.  另一棵树的子树

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
        public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        
        if(root==null){
        
            return false;
        }
        if(eq(root,subRoot)){
        
            return true;
        }//如果当前不满足，继续递归比较root的子树。
        if(isSubtree(root.left,subRoot)||isSubtree(root.right,subRoot)){
        
            return true;
        }
        return false;
    }
        public boolean eq(TreeNode root,TreeNode subRoot){
        
        if(root==null&&subRoot==null){
        //判断是否为相同的树
            return true;
        }
        if(root==null||subRoot==null){
        
            return false;
        }
        if(root.val!=subRoot.val){
        
            return false;
        }
        return eq(root.left,subRoot.left)&&eq(root.right,subRoot.right);
        }
    }

1.  被围绕的区域  
    给你一个 m x n 的矩阵 board ，由若干字符 ‘X’ 和 ‘O’ ，找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。  
    输入：board = \[\[“X”,“X”,“X”,“X”\],\[“X”,“O”,“O”,“X”\],\[“X”,“X”,“O”,“X”\],\[“X”,“O”,“X”,“X”\]\]  
    输出：\[\[“X”,“X”,“X”,“X”\],\[“X”,“X”,“X”,“X”\],\[“X”,“X”,“X”,“X”\],\[“X”,“O”,“X”,“X”\]\]  
    解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 ‘O’ 都不会被填充为 ‘X’。 任何不在边界上，或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

边界上的O是不会被包围的，从边界的O出发，将能够到达的O全部标记，完成之后，将未被标记的O（被包围的）设置为X即可。

class Solution {
        
        int m,n;
        public void solve(char[][] board) {
        
        m=board.length;
        n=board[0].length;
        if(n==0)return;
        for(int i=0;i<m;i++){
        
        dfs(board,i,0);
        dfs(board,i,n-1);
        }
        for(int i=0;i<n;i++){
        
            dfs(board,0,i);
            dfs(board,m-1,i);
        }
        for(int i=0;i<m;i++){
        
            for(int j=0;j<n;j++){
        
                if(board[i][j]=='O'){
        
                    board[i][j]='X';
                }
                if(board[i][j]=='Q'){
        
                    board[i][j]='O';
                }
            }
        }
        }
        public void dfs(char[][] board,int i,int j){
        
            if(i<0||i>=m||j<0||j>=n||board[i][j]!='O'){
        
                return;
            }
            if(board[i][j]=='O'){
        
                board[i][j]='Q';
            }
            dfs(board,i+1,j);
            dfs(board,i-1,j);
            dfs(board,i,j+1);
            dfs(board,i,j-1);
    
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FieXNzd2F0Y2hlcjE_size_16_color_FFFFFF_t_70]: /images/20220829/4c2bb85e64024a5ab50ab77b9550cb09.png