2.深度优先搜索（二）

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

题目汇总

111. 二叉树的最小深度简单

112. 路径总和简单

113. 路径总和 II中等

114. 二叉树展开为链表中等（？）

116. 填充每个节点的下一个右侧节点指针中等

117. 填充每个节点的下一个右侧节点指针 II中等

124. 二叉树中的最大路径和困难（？？？）没做

129. 求根到叶子节点数字之和中等

130. 被围绕的区域中等（？？）

133. 克隆图中等（？？？）没做

111. 二叉树的最小深度简单

给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],
返回它的最小深度 2.

思路：递归

按照 104. 二叉树的最大深度的思路来解题出错

测试用例翻车现场
看了题解之后https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/solution/li-jie-zhe-dao-ti-de-jie-shu-tiao-jian-by-user7208/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 /*叶子节点的定义是左孩子和右孩子都为 null 时叫做叶子节点
当 root 节点左右孩子都为空时，返回 1
当 root 节点左右孩子有一个为空时，返回不为空的孩子节点的深度
当 root 节点左右孩子都不为空时，返回左右孩子较小深度的节点值*/
class Solution {
    public int minDepth(TreeNode root) {//执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户
        if(root == null)
            return 0;
        if(root.left == null && root.right == null)
            return 1;
        int leftDepth = minDepth(root.left);
        int rightDepth = minDepth(root.right);
        if(root.left == null || root.right == null){         
            return leftDepth + rightDepth + 1;
        }
        return Math.min(leftDepth, rightDepth)+1;
    }
}

112. 路径总和简单

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

思路：递归

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {//执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户
        if(root == null)
            return false;
        if(root.left == null && root.right == null)
            return sum - root.val == 0;
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}

113. 路径总和 II中等

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，

返回:
[
[5,4,11,2],
[5,8,4,5]
]

思路：DFS+递归

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {//执行用时 :4 ms, 在所有 Java 提交中击败了14.93%的用户
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        // 从根结点到叶子结点的路径
        List<Integer> path = new ArrayList<>();
        dfs(root, sum, path, res);
        return res;
    }

    private void dfs(TreeNode root, int sum, List<Integer> path, List<List<Integer>> res) {
        if (root == null) {
            return;
        }
        path.add(root.val);
        sum -= root.val;
        if (root.left == null && root.right == null && sum == 0) {
            res.add(path);
            return;
        
        }else{
            dfs(root.left, sum, new ArrayList<>(path), res);
            dfs(root.right, sum, new ArrayList<>(path), res);
        }
    }
}

114. 二叉树展开为链表中等

给定一个二叉树，原地将它展开为一个单链表。
例如，给定二叉树

将其展开为：

思路：递归+DFS

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {//执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户
    public void flatten(TreeNode root) {
        if(root == null)
            return;
        //先把左右子树捋直
        flatten(root.right);
        flatten(root.left);
        TreeNode temp = root.right;//把捋直的右子树备份一下
        root.right = root.left;//把捋直的左子树放到右边
        root.left = null;//把左子树置空
        while(root.right != null){//找到现在右子树的最后一个结点
            root = root.right;
        }
        root.right = temp;//把捋直的原来的右子树接上去
    }
}

116. 填充每个节点的下一个右侧节点指针中等

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
示例：

解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。
提示
你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

思路：递归

左子树的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) //执行用时 :0 ms, 在所有 Java 提交中击败了100.00%
        if(root == null || root.left == null)
            return root;
        root.left.next = root.right;//左子树的next就是右子树
        if(root.next != null){
            root.right.next = root.next.left;//右子树的next就是next节点的左子树
        }
        connect(root.left);
        connect(root.right);
        return root;
    }
}

117. 填充每个节点的下一个右侧节点指针 II中等

给定一个二叉树
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
进阶
你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
示例：

输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。
提示:
树中的节点数小于 6000，-100 <= node.val <= 100

思路：递归

和上一题的主要区别是上题输入是完美二叉树较简单。此题是普通二叉树，考虑情况较为复杂。
看题解注意：递归时要先递归右子树，否则上级节点next关系没建好，下级无法成功getNextNoNullChild
代码来自链接https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii/solution/di-gui-fa-jian-dan-yi-dong-ban-xin-shou-kan-by-lov/

class Solution {
    public Node connect(Node root) {//执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户
        if(root == null)
            return root;
        if(root.left == null && root.right == null){//左右子树都为空
            return root;
        }
        if(root.right == null){//只有左子树
             root.left.next = getNextNoNullChild(root);
        }
        if(root.left == null){//只有右子树
            root.right.next = getNextNoNullChild(root);
        }
        if(root.left != null && root.right != null) {//左右子树都不为空
            root.left.next = root.right;//左子树的next就是右子树
            root.right.next = getNextNoNullChild(root);//右子树的next就是下一级右手第一个
        }
        root.right = connect(root.right);
        root.left = connect(root.left);//这里必须先右后左，否则报错
        return root;
    }
    //根据根节点，找到下一级右手第一个
    private static Node getNextNoNullChild(Node root) {
        while (root.next != null) {
            if (root.next.left != null) {
                return root.next.left;
            }
            if (root.next.right != null) {
                return root.next.right;
            }
            root = root.next;
        }
        return null;
    }
}

124. 二叉树中的最大路径和困难

给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
示例 1:
输入: [1,2,3]
输出: 6
示例 2:
输入: [-10,9,20,null,null,15,7]
输出: 42

129. 求根到叶子节点数字之和中等

给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。
例如，从根到叶子节点路径 1->2->3 代表数字 123。
计算从根到叶子节点生成的所有数字之和。
说明: 叶子节点是指没有子节点的节点。

思路：递归+DFS

class Solution {//执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户
    int result = 0;
    public int sumNumbers(TreeNode root) {
        if(root != null)
            dfs(root, 0);
        return result;
    }
    private void dfs(TreeNode root, int current){
        current = current * 10 + root.val;
        if(root.left == null && root.right == null){
            result += current;
        }
        if(root.left != null){
            dfs(root.left,  current);
        }
        if(root.right != null){
            dfs(root.right,  current);
        }
    }
}

130. 被围绕的区域中等

给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。
找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
示例:
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'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

思路：递归+DFS

主要是寻找和边界联通的 'O'，把这种情况下的 'O' 换成 '#' 作为占位符，待搜索结束之后，遇到 'O' 替换为 'X' （和边界不连通的 'O'）；遇到 '#' ，替换回 'O'(和边界连通的 'O')。

class Solution {//执行用时 :2 ms, 在所有 Java 提交中击败了98.49%的用户
    public void solve(char[][] board) {
        if (board == null || board.length == 0) 
            return;
        int row = board.length;
        int col = board[0].length;
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                boolean isEdge = (i==0 || j==0 || i==row-1 || j==col-1);
                if(isEdge && board[i][j]=='O'){//处理边界上的O
                    dfs(board,i,j);
                }
            }
        }
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';//搜索结束之后，和边界不连通的'O'替换为'X
                }
                if (board[i][j] == '#') {
                    board[i][j] = 'O';//搜索结束之后，和边界连通的'O'（即为'#'）替换回'O'
                }
            }
        }
    }
    //和边界连通的'O'改为'#'
    public void dfs(char[][] board, int i ,int j){
        if(i < 0 || j < 0 || i >= board.length || j >= board[0].length || 
              board[i][j] == '#' || board[i][j] == 'X'){
            return;
        }
        board[i][j] = '#';
        dfs(board, i - 1, j); // 上
        dfs(board, i + 1, j); // 下
        dfs(board, i, j - 1); // 左
        dfs(board, i, j + 1); // 右
    }
}

133. 克隆图中等

给你无向 连通图中一个节点的引用，请你返回该图的 [深拷贝]（克隆）。
图中的每个节点都包含它的值 val（int） 和其邻居的列（list[Node]）。
class Node {
public int val;
public List<Node> neighbors;
}
测试用例格式：
简单起见，每个节点的值都和它的索引相同。例如，第一个节点值为 1（val = 1），第二个节点值为 2（val = 2），以此类推。该图在测试用例中使用邻接列表表示。
邻接列表 是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。
给定节点将始终是图中的第一个节点（值为 1）。你必须将 **给定节点的拷贝 **作为对克隆图的引用返回。

思路：DFS

https://leetcode-cn.com/problems/clone-graph/solution/ke-long-tu-by-leetcode/

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;
    
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/

class Solution {//执行用时 :36 ms, 在所有 Java 提交中击败了81.14%的用户   
    public Node cloneGraph(Node node) {
        //HashMap 存储所有已被访问和复制的节点。key 是原始图中的节点，value 是克隆图中的对应节点
        HashMap<Node,Node> visited = new HashMap<>();
        return dfs(node, visited);  
    }
    private Node dfs(Node node, HashMap<Node,Node> visited){
        if(node == null)
            return null;
        //如果某个节点已经被访问过，则返回其克隆图中的对应节点。
        if(visited.containsKey(node))
            return visited.get(node);
        //为给定节点创建一个克隆
        Node cloneNode = new Node(node.val, new ArrayList());
        visited.put(node, cloneNode);
        //递归调用每个节点的邻接点
        for(Node n : node.neighbors)
            cloneNode.neighbors.add(dfs(n,visited));
        return cloneNode;

    }
}