LeetcodeTop100 刷题总结（二）

LeetCode 热题 100：https://leetcode.cn/studyplan/top-100-liked/

文章目录

八、二叉树
- 94. 二叉树的中序遍历（递归与非递归）
- 补充：144. 二叉树的前序遍历（递归与非递归）
- 补充：145. 二叉树的后序遍历（递归与非递归）
- 104. 二叉树的最大深度
- 226. 翻转二叉树
- 101. 对称二叉树
- 543. 二叉树的直径
- 102. 二叉树的层序遍历
- 108. 将有序数组转换为二叉搜索树
- 98. 验证二叉搜索树
- 230. 二叉搜索树中第 K 小的元素
- 199. 二叉树的右视图
- 114. 二叉树展开为链表
- 105. 从前序与中序遍历序列构造二叉树
- 补充：106. 从中序与后序遍历序列构造二叉树
- 437. 路径总和 III
- 补充：112. 路径总和
- 补充：113. 路径总和 II
- 236. 二叉树的最近公共祖先
- 124. 二叉树中的最大路径和
九、图论
- 200. 岛屿数量
- 994. 腐烂的橘子
- 207. 课程表
- 补充：210. 课程表 II
- 208. 实现 Trie (前缀树)
十、回溯
- 46. 全排列
- 补充：47. 全排列 II
- 78. 子集
- 17. 电话号码的字母组合
- 39. 组合总和
- 补充：40. 组合总和 II
- 补充：216. 组合总和 III
- 22. 括号生成
- 79. 单词搜索
- 131. 分割回文串
- 51. N 皇后

八、二叉树

二叉树的定义：

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;
    }
}

94. 二叉树的中序遍历（递归与非递归）

在这里插入图片描述

递归方式：

class Solution {
    List<Integer> res = new ArrayList<>();
	/**
     * 输入：root = [1,null,2,3] 
     * 输出：[1,3,2]
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        InOrder(root);
        return res;
    }

    public void InOrder(TreeNode root){
        if(root != null){
            InOrder(root.left);
            res.add(root.val);
            InOrder(root.right);
        }
    }
}

非递归方式：

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>(); // 双端队列模拟栈
        List<Integer> list = new ArrayList<>();
        TreeNode p = root;
        while(p != null || !stack.isEmpty()){
            if(p != null){
                stack.push(p);
                p = p.left;
            }else{
                p = stack.pop();
                list.add(p.val);
                p = p.right;
            }
        }
        return list;
    }
}

补充：144. 二叉树的前序遍历（递归与非递归）

题目链接：https://leetcode.cn/problems/binary-tree-preorder-traversal/description/

递归做法：

class Solution {
    List<Integer> list = new ArrayList<>();

    public List<Integer> preorderTraversal(TreeNode root) {
        preOrder(root);
        return list;
    }

    public void preOrder(TreeNode root){
        if(root != null){
            list.add(root.val);
            preOrder(root.left);
            preOrder(root.right);
        }
    }
}

非递归做法：

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>(); // 双端队列模拟栈
        List<Integer> list = new ArrayList<>();
        TreeNode p = root;
        while(p != null || !stack.isEmpty()){
            if(p != null){
                list.add(p.val);
                stack.push(p);
                p = p.left;
            }else{
                p = stack.pop();
                p = p.right;
            }
        }
        return list;
    }
}

补充：145. 二叉树的后序遍历（递归与非递归）

题目链接：https://leetcode.cn/problems/binary-tree-postorder-traversal/description/

递归做法：

class Solution {
    List<Integer> list = new ArrayList<>();

    public List<Integer> postorderTraversal(TreeNode root) {
        postOrder(root);
        return list;
    }

    public void postOrder(TreeNode root){
        if(root != null){
            postOrder(root.left);
            postOrder(root.right);
            list.add(root.val);
        }
    }
}

非递归做法：

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode p, r;
        p = root;
        r = null;
        while(p != null || !stack.isEmpty()){
            if(p != null){ // 走到最左边
                stack.push(p);
                p = p.left;
            }else{ // 向右
                p = stack.peek(); // 得到栈顶元素
                if(p.right != null && p.right != r){ // 右子树存在，且未访问
                    p = p.right;
                }else{ // 否则弹出节点并访问
                    p = stack.pop();
                    list.add(p.val);
                    r = p; // 记录最近访问节点
                    p = null; // 节点访问后，重置 p
                }
            }
        }
        return list;
    }
}

104. 二叉树的最大深度

在这里插入图片描述

class Solution {
	/**
     * 输入：root = [3,9,20,null,null,15,7]
     * 输出：3
     */
    public int maxDepth(TreeNode root) {
        return getMaxDepth(root);
    }

    private int getMaxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = getMaxDepth(root.left);
        int right = getMaxDepth(root.right);
        return Math.max(left, right) + 1;
    }
}

226. 翻转二叉树

在这里插入图片描述

class Solution {
    public TreeNode invertTree(TreeNode root) {
        reverseTree(root);
        return root;
    }

    private void reverseTree(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        reverseTree(root.left);
        reverseTree(root.right);
    }
}

101. 对称二叉树

在这里插入图片描述

class Solution {
	/**
     * 输入：root = [1,2,2,3,4,4,3]
     * 输出：true
     */
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return recur(root.left, root.right);
    }

    public boolean recur(TreeNode l, TreeNode r) {
        if (l == null && r == null) {
            return true;
        }
        if (l == null || r == null || l.val != r.val) {
            return false;
        }
        return recur(l.left, r.right) && recur(l.right, r.left);
    }
}

543. 二叉树的直径

在这里插入图片描述

class Solution {
    int diam;

    /**
     * 输入：root = [1,2,3,4,5]
     * 输出：3
     * 解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
     */
    public int diameterOfBinaryTree(TreeNode root) {
        getMaxDepth(root);
        return diam;
    }

    public int getMaxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = getMaxDepth(root.left);
        int right = getMaxDepth(root.right);
        diam = Math.max(diam, left + right);
        return Math.max(left, right) + 1;
    }
}

102. 二叉树的层序遍历

思路：使用 Deque 模拟队列数据结构，每次进队将一层节点出队，并将下一层节点进队。

在这里插入图片描述

class Solution {
	/**
     * 输入：root = [3,9,20,null,null,15,7]
     * 输出：[[3],[9,20],[15,7]]
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Deque<TreeNode> queue = new LinkedList<>();
        if (root != null) {
            queue.add(root);
        }
        while (!queue.isEmpty()) {
            int size = queue.size(); // 当前队列中节点数量 size
            List<Integer> list = new ArrayList<>();
            for (int i = size; i > 0; i--) { // 循环 size 次，存储该层节点
                TreeNode node = queue.remove();
                list.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            res.add(list);
        }
        return res;
    }
}

注意：每次循环提前求出队列中节点数量，是因为如果没有提前求出 for (int i = 0; i < queue.size; i++)，由于队列的节点数量是变化的，循环结束的条件会发生变化。

108. 将有序数组转换为二叉搜索树

题意要求：将有序数组转换为平衡二叉搜索树，这里可以借鉴二分查找的思路。

在这里插入图片描述

class Solution {
	/**
     * 输入：nums = [-10,-3,0,5,9]
     * 输出：[0,-3,9,-10,null,5]
     * 解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案
     */
    public TreeNode sortedArrayToBST(int[] nums) {
        return buildBST(nums, 0, nums.length - 1);
    }

    private TreeNode buildBST(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }
        int mid = left - (left - right) / 2; // 防溢出
        TreeNode node = new TreeNode(nums[mid]);
        node.left = buildBST(nums, left, mid - 1);
        node.right = buildBST(nums, mid + 1, right);
        return node;
    }
}

98. 验证二叉搜索树

思路：二叉搜索树中序遍历是递增的，因此可以利用栈辅助完成中序遍历的同时来验证是否是二叉搜索树。

class Solution {
	/**
     * 输入：root = [2,1,3]
     * 输出：true
     */
    public boolean isValidBST(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        long val = Long.MIN_VALUE;
        TreeNode p = root;
        while (!stack.isEmpty() || p != null) {
            if (p != null) {
                stack.push(p);
                p = p.left;
            } else {
                TreeNode top = stack.pop();
                if (val >= top.val) {
                    return false;
                }
                val = top.val;
                p = top.right;
            }
        }
        return true;
    }
}

也可使用递归的思路：

class Solution {
    long max = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if(root == null){
            return true;
        }
        if(!isValidBST(root.left)){
            return false;
        }
        if(root.val <= max){
            return false;
        }else{
            max = root.val;
        }
        return isValidBST(root.right);
    }
}

230. 二叉搜索树中第 K 小的元素

思路同上，使用栈进行中序遍历的同时，查询第 K 小的元素。

在这里插入图片描述

class Solution {
	/**
     * 输入：root = [3,1,4,null,2], k = 1
     * 输出：1
     */
    public int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode p = root;
        while (!stack.isEmpty() || p != null) {
            if (p != null) {
                stack.push(p);
                p = p.left;
            } else {
                p = stack.pop();
                if (--k == 0) {
                    return p.val;
                }
                p = p.right;
            }
        }
        return 0;
    }
}

199. 二叉树的右视图

借鉴层序遍历算法，每次取每一层最后一个元素。

在这里插入图片描述

class Solution {
	/**
     * 输入: [1,2,3,null,5,null,4]
     * 输出: [1,3,4]
     */
    public List<Integer> rightSideView(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        Deque<TreeNode> queue = new LinkedList<>();
        List<Integer> res = new ArrayList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = size; i > 0; i--) {
                TreeNode node = queue.remove();
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
                if (i == 1) {
                    res.add(node.val);
                }
            }
        }
        return res;
    }
}

114. 二叉树展开为链表

思路：
① 将左子树的最右节点指向右子树的根节点；
② 将左子树接到右子树的位置；
③ 处理右子树的根节点。
一直重复上边的过程，直到新的右子树为 null。

在这里插入图片描述

class Solution {
	/**
     * 输入：root = [1,2,5,3,4,null,6]
     * 输出：[1,null,2,null,3,null,4,null,5,null,6]
     */
    public void flatten(TreeNode root) {
        TreeNode p = root;
        while (p != null) {
            if (p.left != null) {
                TreeNode pLeft = p.left;
                TreeNode pLeftRight = p.left;
                while (pLeftRight.right != null) { // 查询左子树的最右节点
                    pLeftRight = pLeftRight.right;
                }
                pLeftRight.right = p.right;
                p.right = pLeft;
                p.left = null;
            }
            p = p.right;
        }
    }
}

105. 从前序与中序遍历序列构造二叉树

思路：团体程序设计天梯赛-练习集 L2-011 玩转二叉树 (25分) 先序中序建树思路详解
在这里插入图片描述

class Solution {
    /**
     * 输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
     * 输出: [3,9,20,null,null,15,7]
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) { // 先序，中序
        return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }

    /**
     * 先序中序构建二叉树
     *
     * @param preorder 先序遍历
     * @param preLeft 先序左边界
     * @param preRight 先序右边界
     * @param inorder 中序遍历
     * @param inLeft 中序左边界
     * @param inRight 中序右边界
     * @return 根节点
     */
    public TreeNode build(int[] preorder, int preLeft, int preRight, int[] inorder, int inLeft, int inRight) {
        if (inLeft > inRight || preLeft > preRight) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[preLeft]); // 先序遍历的第一个节点是根节点
        int rootInd = inLeft; // root 代表中序遍历数组中的根节点的索引
        for (int i = inLeft; i <= inRight; i++) {
            if (inorder[i] == preorder[preLeft]) {
                rootInd = i;
                break;
            }
        }
        int len = rootInd - inLeft; // 左子树的长度
        // 先序（根左右）：左边界+1、左边界+长度，中序（左根右）：左边界、根节点位置-1
        root.left = build(preorder, preLeft + 1, preLeft + len, inorder, inLeft, rootInd - 1);
        // 先序（根左右）：左边界+长度+1、右边界，中序（左根右）：根节点位置+1、右边界
        root.right = build(preorder, preLeft + len + 1, preRight, inorder, rootInd + 1, inRight);
        return root;
    }
}

补充：106. 从中序与后序遍历序列构造二叉树

题目链接：https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/

class Solution {
    /**
     * 输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
     * 输出：[3,9,20,null,null,15,7]
     */
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return build(postorder, 0, postorder.length - 1, inorder, 0, inorder.length - 1);
    }

    /**
     * 后序中序构建二叉树
     *
     * @param postorder 后序遍历
     * @param postLeft 后序左边界
     * @param postRight 后序右边界
     * @param inorder 中序遍历
     * @param inLeft 中序左边界
     * @param inRight 中序右边界
     * @return 根节点
     */
    private TreeNode build(int[] postorder, int postLeft, int postRight, int[] inorder, int inLeft, int inRight) {
        if (postLeft > postRight || inLeft > inRight) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[postRight]);
        int rootInd = inLeft;
        for (int i = inLeft; i <= inRight; i++) {
            if(inorder[i] == postorder[postRight]){
                rootInd = i;
                break;
            }
        }
        int len = rootInd - inLeft; // 左子树节长度
        // 后序（左右根）：左边界、左边界+长度-1；中序（左根右）：左边界、根节点位置-1
        root.left = build(postorder, postLeft, postLeft + len -1, inorder, inLeft, rootInd-1);
        // 后序（左右根）：左边界+长度、右边界-1，中序（左根右）：根节点位置+1、右边界
        root.right = build(postorder, postLeft + len, postRight-1, inorder, rootInd + 1, inRight);
        return root;
    }
}

437. 路径总和 III

思路：以当前节点为止，每次去查看之前的的 map 集合中是否还存在目标前缀和。
①
/
②
/
③

假设目标和为 5，节点 1 的前缀和为：1，节点 3 的前缀和为: 1+2+3 = 6，那么 pre(3) - pre(1) = 5
所以从节点 1 到节点 3 之间有一条路径长度为 5。

在这里插入图片描述

class Solution {
    // key:前缀和，value:前缀和的数量（状态会恢复）
    Map<Long, Integer> map;

	/**
     * 输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
     * 输出：3
     * 解释：和等于 8 的路径有 3 条
     */
    public int pathSum(TreeNode root, int targetSum) {
        map = new HashMap<>();
        map.put(0l, 1);
        return backtrack(root, 0L, targetSum);
    }

    private int backtrack(TreeNode root, Long curr, int target) {
        if (root == null) {
            return 0;
        }
        int res = 0;
        curr += root.val;
        
        // 以当前节点为止，去查看从前的 map 集合中是否还存在目标前缀和
        res += map.getOrDefault(curr - target, 0);

        // 存储路径的原因是可能节点的前缀和存在相等的情况：
        //              2
        //             /
        //            0
        //           /
        //          4
        // 从节点 2 到节点 4 有两条路径长度等于2
        map.put(curr, map.getOrDefault(curr, 0) + 1);
        int left = backtrack(root.left, curr, target);
        int right = backtrack(root.right, curr, target);
        res += left + right;

        // 状态恢复
        map.put(curr, map.get(curr) - 1);
        return res;
    }
}

补充：112. 路径总和

题目链接：https://leetcode.cn/problems/path-sum/description/

在这里插入图片描述

class Solution {
	/**
     * 输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
     * 输出：true
     * 解释：等于目标和的根节点到叶节点路径如上图所示
     */
    public boolean hasPathSum(TreeNode root, int targetSum) {
        return backtrack(root, 0, targetSum);
    }

    private boolean backtrack(TreeNode root, int curr, int target) {
        if (root == null) {
            return false;
        }
        curr += root.val;
        if (root.left == null && root.right == null) {
            return curr == target;
        }
        boolean left = backtrack(root.left, curr, target);
        boolean right = backtrack(root.right, curr, target);
        return left || right;
    }
}

补充：113. 路径总和 II

题目链接：https://leetcode.cn/problems/path-sum-ii/description/

在这里插入图片描述

class Solution {
    List<List<Integer>> res;

	/**
     * 输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
     * 输出：[[5,4,11,2],[5,8,4,5]]
     */
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        res = new ArrayList<>();
        backtrack(root, 0, targetSum, new ArrayList<>());
        return res;
    }

    private void backtrack(TreeNode root, int curr, int target, List<Integer> path) {
        if (root == null) {
            return;
        }
        curr += root.val;
        path.add(root.val);
        if (root.left == null && root.right == null && curr == target) {
            res.add(new ArrayList<>(path));
        }
        backtrack(root.left, curr, target, path);
        backtrack(root.right, curr, target, path);
        path.remove(path.size() - 1); // 恢复状态
    }
}

236. 二叉树的最近公共祖先

思路参考：236. 二叉树的最近公共祖先（DFS ，清晰图解）

在这里插入图片描述

class Solution {
	/**
     * 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
     * 输出：3
     * 解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return dfs(root, p, q);
    }

    private TreeNode dfs(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (root == p || root == q) {
            return root;
        }
        TreeNode left = dfs(root.left, p, q);
        TreeNode right = dfs(root.right, p, q);
        if (left != null && right != null) {
            return root;
        } else if (left != null) {
            return left;
        } else if (right != null) {
            return right;
        } else {
            return null;
        }
    }
}

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

在这里插入图片描述

class Solution {
    private int maxPath = Integer.MIN_VALUE;

	/**
     * 输入：root = [-10,9,20,null,null,15,7]
     * 输出：42
     * 解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
     */
    public int maxPathSum(TreeNode root) {
        getMaxPath(root);
        return maxPath;
    }

    private int getMaxPath(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftMaxPath = Math.max(0, getMaxPath(root.left));
        int rightMaxPath = Math.max(0, getMaxPath(root.right));
        maxPath = Math.max(leftMaxPath + root.val + rightMaxPath, maxPath);
        return Math.max(leftMaxPath, rightMaxPath) + root.val;
    }
}

九、图论

200. 岛屿数量

class Solution {
 	/**
     * 输入：grid = [
     *   ["1","1","1","1","0"],
     *   ["1","1","0","1","0"],
     *   ["1","1","0","0","0"],
     *   ["0","0","0","0","0"]
     * ]
     * 输出：1
     */
    public int numIslands(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j, m, n);
                    res++;
                }
            }
        }
        return res;
    }

    private void dfs(char[][] grid, int x, int y, int m, int n) {
        if (0 <= x && x < m && 0 <= y && y < n && grid[x][y] == '1') {
            grid[x][y] = '0';
            dfs(grid, x, y - 1, m, n); // 左上右下
            dfs(grid, x - 1, y, m, n);
            dfs(grid, x, y + 1, m, n);
            dfs(grid, x + 1, y, m, n);
        }
    }
}

994. 腐烂的橘子

思路：遍历的方式参考树的层序遍历，区别在于题目刚开始的入队的节点可能有多个。

在这里插入图片描述

class Solution {
	/**
     * 输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
     * 输出：4
     */
    public int orangesRotting(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        Deque<Point> queue = new LinkedList<>();
        int flesh = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2) {
                    queue.add(new Point(i, j));
                }
                if (grid[i][j] == 1) {
                    flesh++;
                }
            }
        }
        if (flesh == 0) {
            return 0;
        }

        int res = 0;
        int[][] dirs = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}}; // 左上右下四个方向
        while (!queue.isEmpty() && flesh > 0) { // 注意：如果不用 flesh 做判断，队列中还存在节点，因此还会再循环一轮
            int size = queue.size();
            res++;
            for (int i = size; i > 0; i--) {
                Point point = queue.remove();
                int x = point.x;
                int y = point.y;
                for (int[] dir : dirs) {
                    int newX = x + dir[0];
                    int newY = y + dir[1];
                    if (0 <= newX && newX < m && 0 <= newY && newY < n && grid[newX][newY] == 1) {
                        grid[newX][newY] = 2;
                        flesh--;
                        queue.add(new Point(newX, newY));
                    }
                }
            }
        }
        return flesh == 0 ? res : -1;
    }

    class Point {
        int x;

        int y;

        public Point() {
        }

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

207. 课程表

思路：拓扑排序

class Solution {
    /**
     * 输入：numCourses = 2, prerequisites = [[1,0]]
     * 输出：true
     * 解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> neighborTable = buildNeighborTable(numCourses, prerequisites);
        Deque<Integer> stack = new LinkedList<>(); // 用来存储入度为0的节点
        int count = 0; // 用来记录拓扑排序中的节点数量
        int[] indegree = new int[numCourses]; // 存储每个节点的入度
        for (int[] prerequisite : prerequisites) {
            indegree[prerequisite[0]]++;
        }
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                stack.push(i);
            }
        }
        while (!stack.isEmpty()) {
            Integer pop = stack.pop();
            count++;
            for (Integer ind : neighborTable.get(pop)) { // 邻接表中当前节点所关联的节点入度-1
                indegree[ind]--;
                if (indegree[ind] == 0) {
                    stack.push(ind);
                }
            }
        }
        return count == numCourses;
    }

    private List<List<Integer>> buildNeighborTable(int numCourses, int[][] prerequisites) {
        List<List<Integer>> neighborTable = new ArrayList<>(numCourses);
        for (int i = 0; i < numCourses; i++) {
            neighborTable.add(new ArrayList<>());
        }
        for (int i = 0; i < prerequisites.length; i++) { // 构造邻接表
            neighborTable.get(prerequisites[i][1]).add(prerequisites[i][0]);
        }
        return neighborTable;
    }
}

补充：210. 课程表 II

题目链接：https://leetcode.cn/problems/course-schedule-ii/description/

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<List<Integer>> neighborTable = buildNeighborTable(numCourses, prerequisites);
        Deque<Integer> stack = new LinkedList<>(); // 用来存储入度为0的节点
        int count = 0; // 用来记录拓扑排序中的节点数量
        int[] topologies = new int[numCourses];
        int[] indegree = new int[numCourses]; // 存储每个节点的入度
        for (int[] prerequisite : prerequisites) {
            indegree[prerequisite[0]]++;
        }
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                stack.push(i);
            }
        }
        while (!stack.isEmpty()) {
            Integer pop = stack.pop();
            topologies[count++] = pop;
            for (Integer ind : neighborTable.get(pop)) { // 邻接表中当前节点所关联的节点入度-1
                indegree[ind]--;
                if (indegree[ind] == 0) {
                    stack.push(ind);
                }
            }
        }

        return count == numCourses ? topologies : new int[0];
    }

    private List<List<Integer>> buildNeighborTable(int numCourses, int[][] prerequisites) {
        List<List<Integer>> neighborTable = new ArrayList<>(numCourses);
        for (int i = 0; i < numCourses; i++) {
            neighborTable.add(new ArrayList<>());
        }
        for (int i = 0; i < prerequisites.length; i++) { // 构造邻接表
            neighborTable.get(prerequisites[i][1]).add(prerequisites[i][0]);
        }
        return neighborTable;
    }
}

208. 实现 Trie (前缀树)

class Trie {
    class Node {
        Boolean isEnd;
        Node[] next;

        public Node() {
            this.isEnd = false;
            this.next = new Node[26];
        }
    }

    private final Node root;

    public Trie() {
        root = new Node();
    }

    public void insert(String word) {
        Node node = root;
        for (char ch : word.toCharArray()) {
            if (node.next[ch - 'a'] == null) {
                node.next[ch - 'a'] = new Node();
            }
            node = node.next[ch - 'a'];
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        Node node = root;
        for (char ch : word.toCharArray()) {
            if (node.next[ch - 'a'] == null) {
                return false;
            }
            node = node.next[ch - 'a'];
        }
        return node.isEnd;
    }

    public boolean startsWith(String prefix) {
        Node node = root;
        for (char ch : prefix.toCharArray()) {
            if (node.next[ch - 'a'] == null) {
                return false;
            }
            node = node.next[ch - 'a'];
        }
        return true;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

十、回溯

注：回溯的题目大部分都是暴力搜索+剪枝，因此不做过多赘述。

46. 全排列

题目：给定一个 不含重复数字 的数组 nums ，返回其所有可能的全排列。你可以按任意顺序返回答案。

在这里插入图片描述

class Solution {
	/**
     * 输入：nums = [1,2,3]
     * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
     */
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        int len = nums.length;
        boolean[] visited = new boolean[len];
        dfs(res, nums, visited, new ArrayList<>());
        return res;
    }

    private void dfs(List<List<Integer>> res, int[] nums, boolean[] visited, List<Integer> list) {
        if (list.size() == nums.length) {
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!visited[i]) {
                list.add(nums[i]);
                visited[i] = true;
                dfs(res, nums, visited, list);
                list.remove(list.size() - 1);
                visited[i] = false;
            }
        }
    }
}

补充：47. 全排列 II

题目链接：https://leetcode.cn/problems/permutations-ii/

题目：给定一个 包含重复数字 的数组 nums ，返回其所有可能的全排列。你可以按任意顺序返回答案。

在这里插入图片描述

class Solution {
    /**
     * 输入：nums = [1,1,2]
     * 输出：[[1,1,2],[1,2,1],[2,1,1]]
     */
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums); // 排序
        boolean[] visited = new boolean[nums.length];
        backtrack(visited, nums, new ArrayList<>(), res);
        return res;
    }

    private void backtrack(boolean[] visited, int[] nums, List<Integer> list, List<List<Integer>> res) {
        if (list.size() == nums.length) {
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!visited[i]) {
                if (i > 0 && nums[i] == nums[i - 1] && visited[i - 1] == false) { // 剪枝
                    continue;
                }
                visited[i] = true;
                list.add(nums[i]);
                backtrack(visited, nums, list, res);
                list.remove(list.size() - 1);
                visited[i] = false;
            }
        }
    }
}

78. 子集

在这里插入图片描述

class Solution {
    /**
     * 输入：nums = [1,2,3] 
     * 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
     */
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        int len = nums.length;
        boolean[] visited = new boolean[len];
        dfs(nums, 0, new ArrayList<>(), res);
        return res;
    }

    private void dfs(int[] nums, int ind, List<Integer> list, List<List<Integer>> res) {
        if (ind >= nums.length) {
            res.add(new ArrayList<>(list));
            return;
        }
        list.add(nums[ind]);
        dfs(nums, ind + 1, list, res);
        list.remove(list.size() - 1);
        dfs(nums, ind + 1, list, res);
    }
}

17. 电话号码的字母组合

class Solution {
    Map<Character, String> map = new HashMap<>();
    String digits;

	/**
     * 输入：digits = "23"
     * 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
     */
    public List<String> letterCombinations(String digits) {
        if (digits.length() == 0) {
            return new ArrayList<>();
        }
        map.put('2', "abc");
        map.put('3', "def");
        map.put('4', "ghi");
        map.put('5', "jkl");
        map.put('6', "mno");
        map.put('7', "pqrs");
        map.put('8', "tuv");
        map.put('9', "wxyz");
        this.digits = digits;
        List<String> res = new ArrayList<>();
        backtrack(0, new StringBuilder(), res);
        return res;
    }

    private void backtrack(int ind, StringBuilder builder, List<String> res) {
        if (ind == digits.length()) {
            res.add(new String(builder));
            return;
        }
        String words = map.get(digits.charAt(ind));
        for (char ch : words.toCharArray()) {
            builder.append(ch);
            backtrack(ind+1, builder, res);
            builder.deleteCharAt(builder.length() - 1);
        }
    }
}

39. 组合总和

题目：给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。
candidates 中的同一个数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

class Solution {
    int[] candidates;

	/**
     * 输入：candidates = [2,3,6,7], target = 7
     * 输出：[[2,2,3],[7]]
     * 解释：
     * 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
     * 7 也是一个候选， 7 = 7 。
     * 仅有这两种组合。
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        this.candidates = candidates;
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(candidates);
        backtrack(target, 0, new ArrayList<>(), res);
        return res;
    }

    private void backtrack(int target, int ind, List<Integer> temp, List<List<Integer>> res) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            res.add(new ArrayList<>(temp));
            return;
        }
        for (int i = ind; i < candidates.length; i++) {
            if (target - candidates[i] < 0) {
                break;
            }
            temp.add(candidates[i]);
            backtrack(target - candidates[i], i, temp, res);
            temp.remove(temp.size() - 1);
        }
    }
}

补充：40. 组合总和 II

题目链接：https://leetcode.cn/problems/combination-sum-ii/description/

与上道题目不同的是，解集不能包含重复的组合，参考：全排列 II：

class Solution {
    int[] candidates;

    /**
     * 输入: candidates = [10,1,2,7,6,1,5], target = 8,
     * 输出: [[1,1,6],[1,2,5],[1,7],[2,6]]
     */
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        this.candidates = candidates;
        List<List<Integer>> res = new ArrayList<>();
        boolean[] visited = new boolean[candidates.length];
        Arrays.sort(candidates);
        backtrack(target, 0, visited, new ArrayList<>(), res);
        return res;
    }

    private void backtrack(int target, int ind, boolean[] visited, List<Integer> list, List<List<Integer>> res) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i = ind; i < candidates.length; i++) {
            if (!visited[i]) {
                if (target - candidates[i] < 0) {
                    break;
                }
                if (i != 0 && candidates[i - 1] == candidates[i] && !visited[i - 1]) {
                    continue;
                }
                list.add(candidates[i]);
                visited[i] = true;
                backtrack(target - candidates[i], i + 1, visited, list, res);
                visited[i] = false;
                list.remove(list.size() - 1);
            }
        }
    }
}

补充：216. 组合总和 III

题目链接：https://leetcode.cn/problems/combination-sum-iii/description/

题目：找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
① 只使用数字 1 到 9
② 每个数字最多使用一次
③ 返回所有可能的有效组合的列表。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

class Solution {
    List<List<Integer>> res;
    int size;

	/**
     * 输入: k = 3, n = 7
     * 输出: [[1,2,4]]
     * 解释: 1 + 2 + 4 = 7 没有其他符合的组合了。
     */
    public List<List<Integer>> combinationSum3(int k, int n) {
        this.res = new ArrayList<>();
        this.size = k;
        backtrack(1, n, new ArrayList<>());
        return res;
    }

    private void backtrack(int ind, int target, List<Integer> list) {
        if (target == 0) {
            if (size == list.size()) {
                res.add(new ArrayList<>(list));
            }
            return;
        }
        for (int i = ind; i < 10; i++) {
            if (target - i < 0) {
                break;
            }
            list.add(i);
            backtrack(i + 1, target - i, list);
            list.remove(list.size() - 1);
        }
    }
}

22. 括号生成

思路：每次优先选左括号，然后再选右括号。

class Solution {
	/**
     * 输入：n = 3
     * 输出：["((()))","(()())","(())()","()(())","()()()"]
     */
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        backtrack(n, n, new StringBuilder(), res);
        return res;
    }

     private void backtrack(int left, int right, StringBuilder builder, List<String> res) {
        if (left > right) { // 左括号少，剪枝
            return;
        }
        if (left == 0 && right == 0) {
            res.add(builder.toString());
            return;
        }
        if (left != 0) { // 优先选左
            builder.append('(');
            backtrack(left - 1, right, builder, res);
            builder.deleteCharAt(builder.length() - 1);
        }
        builder.append(')');
        backtrack(left, right - 1, builder, res);
        builder.deleteCharAt(builder.length() - 1);
    }
}

79. 单词搜索

在这里插入图片描述

class Solution {
    /**
     * 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
     * 输出：true
     */
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == word.charAt(0) && dfs(word, i, j, 0, board)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(String word, int x, int y, int ind, char[][] board) {
        if (ind >= word.length()) {
            return true;
        }
        if (0 <= x && x < board.length && 0 <= y && y < board[0].length && board[x][y] == word.charAt(ind)
            && board[x][y] != '\0') {
            char ch = board[x][y];
            board[x][y] = '\0';
            boolean left = dfs(word, x, y - 1, ind + 1, board); // 左上右下
            boolean up = dfs(word, x - 1, y, ind + 1, board);
            boolean right = dfs(word, x, y + 1, ind + 1, board);
            boolean down = dfs(word, x + 1, y, ind + 1, board);
            board[x][y] = ch;
            return left || up || right || down;
        }
        return false;
    }
}

131. 分割回文串

class Solution {
    List<List<String>> res;
    
	/**
	 * 输入：s = "aab"
	 * 输出：[["a","a","b"],["aa","b"]]
     */
    public List<List<String>> partition(String s) {
        res = new ArrayList<>();
        backtrack(s, 0, new ArrayList<>());
        return res;
    }

    private void backtrack(String s, int ind, List<String> list) {
        if (ind >= s.length()) {
            res.add(new ArrayList<>(list));
            return;
        }

        for (int i = ind; i < s.length(); i++) {
            if (isPalindrome(s, ind, i)) {
                list.add(s.substring(ind, i + 1));
                backtrack(s, i + 1, list);
                list.remove(list.size() - 1);
            }
        }
    }

    private boolean isPalindrome(String s, int start, int end) {
        while (start <= end) {
            if (s.charAt(start) != s.charAt(end)) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
}

51. N 皇后

在这里插入图片描述

class Solution {
	/**
     * 输入：n = 4
     * 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
     * 解释：如上图所示，4 皇后问题存在两个不同的解法。
     */
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        int[] queenCols = new int[n]; // {1,3,0,2} 存储第i行的皇后在第 queenCols.get(i) 列
        dfs(0, n, queenCols, res);
        return res;
    }

    private List<String> convert(int[] queenCols, int n) {
        List<String> solution = new ArrayList<>();// {1,3,0,2} -> [".Q..","...Q","Q...","..Q."],
        for (Integer col : queenCols) {
            char[] temp = new char[n];
            Arrays.fill(temp, '.');
            temp[col] = 'Q';
            solution.add(new String(temp));
        }
        return solution;
    }

    private void dfs(int row, int n, int[] queenCols, List<List<String>> res) {
        if (row == n) {
            res.add(convert(queenCols, n));
            return;
        }

        for (int col = 0; col < n; col++) { // 对当前行的每一列进行遍历
            if (!isValid(queenCols, row, col)) {
                continue;
            }
            queenCols[row] = col;
            dfs(row + 1, n, queenCols, res);
            queenCols[row] = -1;
        }
    }

    private boolean isValid(int[] queenCols, int row, int col) {
        for (int i = 0; i < row; i++) {
            if (queenCols[i] == col || row - i == col - queenCols[i] || row - i == queenCols[i] - col) {
             	// 同一列；同'\'方向，“行-皇后所在行 == 列-皇后所在列”；同'/'方向，“行-皇后所在行 == 皇后所在列-列”
                return false;
            }
        }
        return true;
    }
}

以上解决方案也适用于：
面试题 08.12. 八皇后：https://leetcode.cn/problems/eight-queens-lcci/description/
52. N 皇后 II：https://leetcode.cn/problems/n-queens-ii/description/