常见算法题

零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回-1 。
你可以认为每种硬币的数量是无限的。
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1

解题思路
动态规划
采用自下而上的方式进行思考。仍定义 F(i)为组成金额 i所需最少的硬币数量，假设在计算F(i) 之前，
我们已经计算出 F(0)-F(i-1)的答案。 则F(i)对应的转移方程应为
F(i)=min[j=0...n-1] F(i-cj)+1
F(3)=min(F(3-c1),F(3-c2),F(3-c3))+1
    =min(F(3-1),F(3-2),F(3-3))+1
    =min(F(2),F(1),F(0))+1
    =min(1,1,0)+1
    =1

代码实现：
public int coinChange(int[] coins, int amount) {
        int max = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, max);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
 }

岛屿数量

给你一个由'1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
 此外，你可以假设该网格的四条边均被水包围。
 输入：grid = [
   ["1","1","1","1","0"],
   ["1","1","0","1","0"],
   ["1","1","0","0","0"],
   ["0","0","0","0","0"]
 ]
 输出：1

 输入：grid = [
   ["1","1","0","0","0"],
   ["1","1","0","0","0"],
   ["0","0","1","0","0"],
   ["0","0","0","1","1"]
 ]
 输出：3
 
 解题思路
      深度优先搜索
      可以将二维网格看成一个无向图，竖直或水平相邻的1之间有边相连。
      为了求出岛屿的数量，我们可以扫描整个二维网格。
      如果一个位置为1，则以其为起始节点开始进行深度优先搜索。在深度优先搜索的过程中，每个搜索到的 1都会被重新标记为0。
      最终岛屿的数量就是我们进行深度优先搜索的次数。
      
 
 代码实现：
 public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int nr = grid.length;
        int nc = grid[0].length;
        int num_islands = 0;
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1') {
                    ++num_islands;
                    dfs(grid, r, c);
                }
            }
        }
        return num_islands;
}
    
void dfs(char[][] grid, int r, int c) {
        int nr = grid.length;
        int nc = grid[0].length;

        if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
            return;
        }
        grid[r][c] = '0';
        dfs(grid, r - 1, c);
        dfs(grid, r + 1, c);
        dfs(grid, r, c - 1);
        dfs(grid, r, c + 1);
}

迷宫问题

int maze[n][m]; 它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
输入：int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
输出：
(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(3,4)
(4,4)


思路：
使用深度优先搜索找到能够到达终点的路径
利用二维顺序表（ArrayList>）保存每一条能够到达终点的路径
找到其中最短的路径输出即可。

   static ArrayList< ArrayList> res = new ArrayList<>();

    public void maze(int[][] maze) {
        int n=maze.length;
        int m=maze[0].length;
        // 第一步
        //创建一个 ArrayList step 记录步数
        ArrayList step = new ArrayList<>();
        //调用 dfs 函数
        dfs(maze,0,0,n,m,step);

        // 第三步
        //得到结果 筛选最短路径
        int size = Integer.MAX_VALUE;
        int index = 0;
        for (int i = 0; i < res.size(); i++) {
            if (res.get(i).size() < size) {
                size = res.get(i).size();
                index = i;
            }
        }

        //第三步
        //将最短路径保存并输出
        step = res.get(index);
        for (int i = 0; i < step.size(); i+=2) {
            System.out.println("(" + step.get(i) + "," + step.get(i+1) + ")");
        }

        // 清空 res 继续下一个迷宫
        // 这一步其实不仅仅是循环输入的时候用到
        //个人觉得清除后可以节省空间。
        res.clear();
    }

    public static void dfs(int[][] maze,int i,int j,int n,int m,ArrayList step) {
        // 越界 、 有墙 、 已经走过
        if (i < 0 || i >= n || j < 0 || j >= m || maze[i][j] == 1 || maze[i][j] == 2) {
            return;
        }
        //如果到达终点
        if (i == n - 1 && j == m - 1) {
            //添加终点坐标
            step.add(i);
            step.add(j);
            res.add(new ArrayList<>(step));
            //回溯
            step.remove(step.size() - 1);
            step.remove(step.size() - 1);
        }else {
            //没有到达终点
            //添加当前坐标
            step.add(i);
            step.add(j);
            //标记为已经走过
            maze[i][j] = 2;
            // 递归
            dfs(maze, i + 1, j, n, m, step);
            dfs(maze, i, j + 1, n, m, step);
            dfs(maze, i - 1, j, n, m, step);
            dfs(maze, i, j - 1, n, m, step);
            // 回溯
            maze[i][j] = 0;
            step.remove(step.size() - 1);
            step.remove(step.size() - 1);
        }
    }

不同路径

一个机器人位于一个 m x n网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下


      动态规划
      我们用 f(i,j)表示从左上角走到(i,j) 的路径数量，其中i 和 j的范围分别是[0,m)和[0,n)。
      由于我们每一步只能从向下或者向右移动一步，因此要想走到(i,j)，
      如果向下走一步，那么会从(i−1,j)走过来；
      如果向右走一步，那么会从(i,j−1)走过来。因此我们可以写出动态规划转移方程：
      f(i,j)=f(i−1,j)+f(i,j−1)
      
 代码实现
 public int uniquePaths(int m, int n) {
        int[][] f = new int[m][n];
        for (int i = 0; i < m; ++i) {
            f[i][0] = 1;
        }
        for (int j = 0; j < n; ++j) {
            f[0][j] = 1;
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                f[i][j] = f[i - 1][j] + f[i][j - 1];
            }
        }
        return f[m - 1][n - 1];
    }

最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

输入：grid = [[1,2,3],[4,5,6]]
输出：12

动态规划
由于路径的方向只能是向下或向右，因此网格的第一行的每个元素只能从左上角元素开始向右移动到达，
网格的第一列的每个元素只能从左上角元素开始向下移动到达，此时的路径是唯一的，因此每个元素对应的最小路径和即为对应的路径上的数字总和。
对于不在第一行和第一列的元素，可以从其上方相邻元素向下移动一步到达，或者从其左方相邻元素向右移动一步到达，
元素对应的最小路径和等于其上方相邻元素与其左方相邻元素两者对应的最小路径和中的最小值加上当前元素的值。
由于每个元素对应的最小路径和与其相邻元素对应的最小路径和有关，因此可以使用动态规划求解。
创建二维数组dp，与原始网格的大小相同，dp[i][j] 表示从左上角出发到 (i,j)(i,j) 位置的最小路径和。显然，dp[0][0]=grid[0][0]。对于dp 中的其余元素，通过以下状态转移方程计算元素值。
当 i>0且j=0 时，dp[i][0]=dp[i−1][0]+grid[i][0]。
当 i=0且 j>0j>0 时，dp[0][j]=dp[0][j−1]+grid[0][j]。
当 i>0且 j>0时，dp[i][j]=min(dp[i−1][j],dp[i][j−1])+grid[i][j]。
最后得到dp[m−1][n−1] 的值即为从网格左上角到网格右下角的最小路径和。


    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int rows = grid.length, columns = grid[0].length;
        int[][] dp = new int[rows][columns];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < rows; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int j = 1; j < columns; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < columns; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[rows - 1][columns - 1];
    }

移动0

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
输入: nums = [0]
输出: [0]

方法一：双指针
      使用双指针，左指针指向当前已经处理好的序列的尾部，右指针指向待处理序列的头部。
      右指针不断向右移动，每次右指针指向非零数，则将左右指针对应的数交换，同时左指针右移。
      注意到以下性质：
      左指针左边均为非零数；
      右指针左边直到左指针处均为零。
      因此每次交换，都是将左指针的零与右指针的非零数交换，且非零数的相对顺序并未改变。
      
代码实现：
public void moveZeroes(int[] nums) {
        int n = nums.length, left = 0, right = 0;
        while (right < n) {
            if (nums[right] != 0) {
                swap(nums, left, right);
                left++;
            }
            right++;
        }
 }

public void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
}

打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，
如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。

解题思路：
如果只有一间房屋，则偷窃该房屋，可以偷窃到最高总金额。如果只有两间房屋，则由于两间房屋相邻，不能同时偷窃，只能偷窃其中的一间房屋，因此选择其中金额较高的房屋进行偷窃，可以偷窃到最高总金额。
      如果房屋数量大于两间，应该如何计算能够偷窃到的最高总金额呢？对于第 k~(k>2)间房屋，有两个选项：
      偷窃第k间房屋，那么就不能偷窃第 k-1间房屋，偷窃总金额为前 k-2间房屋的最高总金额与第 k间房屋的金额之和。
      不偷窃第k间房屋，偷窃总金额为前 k-1间房屋的最高总金额。
     用 dp[i] 表示前 i间房屋能偷窃到的最高总金额，那么就有如下的状态转移方程：
      dp[i]=max(dp[i-2]+nums[i],dp[i-1])
      边界：
      dp[0]=nums[0]  只有一间房屋，则偷窃该房屋
      dp[1]=max(nums[0],nums[1])  只有两间房屋，选择金额较高的
      
      
代码实现：
public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        }
        int[] dp = new int[length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < length; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[length - 1];
    }

买卖股票的最佳时机

给定一个数组 prices，它的第i个元素prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
     
 //全局最低点比较法
    public int maxProfit2(int prices[]) {
        int minprice = Integer.MAX_VALUE;
        int maxprofit = 0;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minprice) {
                minprice = prices[i];
            } else if (prices[i] - minprice > maxprofit) {
                maxprofit = prices[i] - minprice;
            }
        }
        return maxprofit;
    }

子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

 List t = new ArrayList();
    List> ans = new ArrayList>();

    public List> subsets(int[] nums) {
        dfs(0, nums);
        return ans;
    }

    public void dfs(int cur, int[] nums) {
        if (cur == nums.length) {
            ans.add(new ArrayList(t));
            return;
        }
        t.add(nums[cur]);
        dfs(cur + 1, nums);
        t.remove(t.size() - 1);
        dfs(cur + 1, nums);
    }

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

动态规划：f(x)=f(x−1)+f(x−2)
意味着爬到第x级台阶的方案数是爬到第x−1 级台阶的方案数和爬到第x−2级台阶的方案数的和

public int climbStairs(int n) {
        int preOne = 0, preTwo = 0, index = 1;
        for (int i = 1; i <= n; ++i) {
            preOne = preTwo;
            preTwo = index;
            index = preOne + preTwo;
        }
        return index;
    }

跳跃游戏

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

    public boolean canJump(int[] nums) {
        int n = nums.length;
        int rightmost = 0;
        for (int i = 0; i < n; ++i) {
            if (i <= rightmost) {
                rightmost = Math.max(rightmost, i + nums[i]);
                if (rightmost >= n - 1) {
                    return true;
                }
            }
        }
        return false;
    }

旋转图像

给定一个 n×n 的二维矩阵matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

    使用辅助数组
      我们以题目中的示例二
        5 1 9 11    o o o 5
        o o o o     o o o 1
        o o o o  ==>o o o 9
        o o o o     o o o 11
        第一行的第x个元素在旋转后恰好是倒数第一列的第 x个元素。
        对于矩阵中第 i 行的第 j个元素，在旋转后，它出现在倒数第i列的第j个位置
        对于矩阵中的元素matrix[row][col] =>matrix_new[col][n-row-1]
        我们使用一个与 matrix 大小相同的辅助数组matrix_new,临时存储旋转后的结果。
        我们遍历matrix 中的每一个元素，根据上述规则将该元素存放到 matrix_new
        中对应的位置。在遍历完成之后，再将matrix_new中的结果复制到原数组中即可。
        
  public void rotate(int[][] matrix) {
        int n = matrix.length;
        int[][] matrix_new = new int[n][n];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                matrix_new[j][n - i - 1] = matrix[i][j];
            }
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                matrix[i][j] = matrix_new[i][j];
            }
        }
    }       

组合总和

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

 输入：candidates = [2,3,6,7], target = 7
 输出：[[2,2,3],[7]]
 解释：
 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
 7 也是一个候选， 7 = 7 。
 仅有这两种组合

 输入: candidates = [2,3,5], target = 8
 输出: [[2,2,2,2],[2,3,3],[3,5]]
 
 这类寻找所有可行解的题，我们都可以尝试用「搜索回溯」的方法来解决。
      我们定义递归函数 dfs(target,combine,idx) 表示当前在 candidates 数组的第idx 位，还剩 target 要组合，
      已经组合的列表为 combine。递归的终止条件为target≤0 或者 candidates 数组被全部用完。
      那么在当前的函数中，每次我们可以选择跳过不用第idx 个数，即执行 dfs(target,combine,idx+1)。
      也可以选择使用第idx 个数，即执行dfs(target−candidates[idx],combine,idx)，注意到每个数字可以被无限制重复选取，因此搜索的下标仍为idx。
      
  public List> combinationSum(int[] candidates, int target) {
        List> ans = new ArrayList>();
        List combine = new ArrayList();
        dfs(candidates, target, ans, combine, 0);
        return ans;
    }

    public void dfs(int[] candidates, int target, List> ans, List combine, int idx) {

        if (idx == candidates.length) {
            return;
        }
        if (target == 0) {
            ans.add(new ArrayList(combine));
            return;
        }
        // 直接跳过
        dfs(candidates, target, ans, combine, idx + 1);
        // 选择当前数
        if (target - candidates[idx] >= 0) {
            combine.add(candidates[idx]);
            dfs(candidates, target - candidates[idx], ans, combine, idx);
            combine.remove(combine.size() - 1);
        }
    }

二叉树中序遍历

* 给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
* 输入：root = [1,null,2,3]
* 输出：[1,3,2]

 public List inorderTraversal(TreeNode root) {
        List res = new ArrayList();
        inorder(root, res);
        return res;
    }

    public void inorder(TreeNode root, List res) {
        if (root == null) {
            return;
        }
        inorder(root.left, res);
        res.add(root.val);
        inorder(root.right, res);
    }

二叉树前序遍历

* 给你二叉树的根结点 root ，请你将它展开为一个单链表：
*
* 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
* 展开后的单链表应该与二叉树先序遍历顺序相同。
* 输入：root = [1,2,5,3,4,null,6]
* 输出：[1,null,2,null,3,null,4,null,5,null,6]

   public void flatten(TreeNode root) {
        List list = new ArrayList();
        preorderTraversal(root, list);
        int size = list.size();
        for (int i = 1; i < size; i++) {
            TreeNode prev = list.get(i - 1), curr = list.get(i);
            prev.left = null;
            prev.right = curr;
        }
    }

    public void preorderTraversal(TreeNode root, List list) {
        if (root != null) {
            list.add(root);
            preorderTraversal(root.left, list);
            preorderTraversal(root.right, list);
        }
    }

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

* 给定两个整数数组preorder 和 inorder，
* 其中preorder 是二叉树的先序遍历， inorder是同一棵树的中序遍历，请构造二叉树并返回其根节点。
*
* 输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
* 输出: [3,9,20,null,null,15,7]


    private Map indexMap;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        // 构造哈希映射，帮助我们快速定位根节点
        indexMap = new HashMap();
        for (int i = 0; i < n; i++) {
            indexMap.put(inorder[i], i);
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }


    public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left > preorder_right) {
            return null;
        }

        // 前序遍历中的第一个节点就是根节点
        int preorder_root = preorder_left;
        // 在中序遍历中定位根节点
        int inorder_root = indexMap.get(preorder[preorder_root]);

        // 先把根节点建立出来
        TreeNode root = new TreeNode(preorder[preorder_root]);
        // 得到左子树中的节点数目
        int size_left_subtree = inorder_root - inorder_left;
        // 递归地构造左子树，并连接到根节点
        // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
        root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
        // 递归地构造右子树，并连接到根节点
        // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
        root.right = myBuildTree(preorder, inorder,preorder_left + 1 + size_left_subtree, preorder_right, inorder_root + 1, inorder_right);
        return root;
    }

二叉树层序遍历

*给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
*输入：root = [3,9,20,null,null,15,7]
* 输出：[[3],[9,20],[15,7]]

//广度优先搜索
    public List> levelOrder(TreeNode root) {
        List> ret = new ArrayList>();
        if (root == null) {
            return ret;
        }

        Queue queue = new LinkedList();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List level = new ArrayList();
            int currentLevelSize = queue.size();
            for (int i = 1; i <= currentLevelSize; ++i) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            ret.add(level);
        }

        return ret;
    }

最大深度

* 给定一个二叉树，找出其最大深度。
* 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
* 说明:叶子节点是指没有子节点的节点。
* 示例：
* 给定二叉树 [3,9,20,null,null,15,7]，


  * 如果我们知道了左子树和右子树的最大深度 ll 和 rr，那么该二叉树的最大深度即为
     * max(l,r) + 1
     * 左子树和右子树的最大深度又可以以同样的方式进行计算。
     * 因此我们可以用「深度优先搜索」的方法来计算二叉树的最大深度。具体而言，在计算当前二叉树的最大深度时，可以先递归计算出其左子树和右子树的最大深度，
     * 然后在O(1) 时间内计算出当前二叉树的最大深度。递归在访问到空节点时退出。
     
     
public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            int leftHeight = maxDepth(root.left);
            int rightHeight = maxDepth(root.right);
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }

验证二叉树

* 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
* 有效 二叉搜索树定义如下：
* 节点的左子树只包含 小于 当前节点的数。
* 节点的右子树只包含 大于 当前节点的数。
* 所有左子树和右子树自身必须也是二叉搜索树。
* 输入：root = [2,1,3]
* 输出：true


 * 如果该二叉树的左子树不为空，则左子树上所有节点的值均小于它的根节点的值；
     * 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；它的左右子树也为二叉搜索树。
    
    
  public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    public boolean isValidBST(TreeNode node, long lower, long upper) {
        if (node == null) {
            return true;
        }
        if (node.val <= lower || node.val >= upper) {
            return false;
        }
        return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);
    }

不同的二叉树

*给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
* 输入：n = 3
* 输出：5


     * 假设 n 个节点存在二叉排序树的个数是 G (n)，令 f(i) 为以 i 为根的二叉搜索树的个数，则
     * G(n) = f(1) + f(2) + f(3) + f(4) + ... + f(n)G(n)=f(1)+f(2)+f(3)+f(4)+...+f(n)
     * 当 i 为根节点时，其左子树节点个数为 i-1 个，右子树节点为 n-i，则
     * f(i) = G(i-1)*G(n-i)f(i)=G(i−1)∗G(n−i)
     *
     * 综合两个公式可以得到 卡特兰数 公式
     * G(n) = G(0)*G(n-1)+G(1)*(n-2)+...+G(n-1)*G(0)G(n)=G(0)∗G(n−1)+G(1)∗(n−2)+...+G(n−1)∗G(0)
     
     
     public int numTrees(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;

        for(int i = 2; i < n + 1; i++) {
            for(int j = 1; j < i + 1; j++) {
                dp[i] += dp[j-1] * dp[i-j];
            }
        }

        return dp[n];
    }

对称二叉树

* 给你一个二叉树的根节点 root ， 检查它是否轴对称
* 输入：root = [1,2,2,3,4,4,3]
* 输出：true

     * 递归
     * 通过「同步移动」两个指针的方法来遍历这棵树，p指针和q 指针一开始都指向这棵树的根，
     * 随后 p右移时，q左移，p左移时，q右移。每次检查当前 p和 q节点的值是否相等，如果相等再判断左右子树是否对称。
     
     
 public boolean isSymmetric(TreeNode root) {
        return check(root, root);
    }

    public boolean check(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
    }

二叉树中的最大路径和

* 路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。
* 该路径 至少包含一个节点，且不一定经过根节点。
* 路径和 是路径中各节点值的总和。
* 给你一个二叉树的根节点 root ，返回其最大路径和 。
* 输入：root = [1,2,3]
* 输出：6
* 解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
*
* 输入：root = [-10,9,20,null,null,15,7]
* 输出：42
* 解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42


 int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }

    public int maxGain(TreeNode node) {
        if (node == null) {
            return 0;
        }

        // 递归计算左右子节点的最大贡献值
        // 只有在最大贡献值大于 0 时，才会选取对应子节点
        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);

        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int priceNewpath = node.val + leftGain + rightGain;

        // 更新答案
        maxSum = Math.max(maxSum, priceNewpath);

        // 返回节点的最大贡献值
        return node.val + Math.max(leftGain, rightGain);
    }

翻转二叉树

* 给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节
* 输入：root = [4,2,7,1,3,6,9]
* 输出：[4,7,2,9,6,3,1]

public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }

二叉树的最近公共祖先

* 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
*
* 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，
* 最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
*
* 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
* 输出：3
* 解释：节点 5 和节点 1 的最近公共祖先是节点 3 。


  private TreeNode ans =null;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        this.dfs(root, p, q);
        return this.ans;
    }

    private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return false;
        }
        boolean lson = dfs(root.left, p, q);
        boolean rson = dfs(root.right, p, q);
        if ((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson))) {
            ans = root;
        }
        return lson || rson || (root.val == p.val || root.val == q.val);
    }

合并二叉树

* 给你两棵二叉树： root1 和 root2 。
* 想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：
* 如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
* 返回合并后的二叉树。
* 注意: 合并过程必须从两个树的根节点开始。
*
* 输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
* 输出：[3,4,5,5,4,null,7]

  // 深度
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null) {
            return t2;
        }
        if (t2 == null) {
            return t1;
        }
        TreeNode merged = new TreeNode(t1.val + t2.val);
        merged.left = mergeTrees(t1.left, t2.left);
        merged.right = mergeTrees(t1.right, t2.right);
        return merged;
    }

合并两个有序链表

* 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
* 输入：l1 = [1,2,4], l2 = [1,3,4]
* 输出：[1,1,2,3,4,4]


    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 判断链表是否为空
        if (l1 == null || l2 == null) {
            return l1 != null ? l1 : l2;
        }

        if (l1.val < l2.val) {
            //判断 l1 和 l2 哪一个链表的头节点的值更小，然后递归地决定下一个添加到结果里的节点
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }

合并K个排序链表

* 给你一个链表数组，每个链表都已经按升序排列。
* 请你将所有链表合并到一个升序链表中，返回合并后的链表
* 输入：lists = [[1,4,5],[1,3,4],[2,6]]
* 输出：[1,1,2,3,4,4,5,6]
* 解释：链表数组如下：
* [
*   1->4->5,
*   1->3->4,
*   2->6
* ]
* 将它们合并到一个有序链表中得到。
* 1->1->2->3->4->4->5->6


   public ListNode mergeKLists(ListNode[] lists) {
        ListNode ans = null;
        for (int i = 0; i < lists.length; ++i) {
            ans = mergeTwoLists(ans, lists[i]);
        }
        return ans;
    }

    // 迭代
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 哨兵节点 prehead
        ListNode prehead = new ListNode(-1);
        //prev 指针，调整它的next指针
        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                //l1 当前的节点接在 prev 节点的后面同时将 l1 指针往后移一位。
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }

删除链表的倒数第N个结点

* 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
* 输入：head = [1,2,3,4,5], n = 2
* 输出：[1,2,3,5]

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        int length = getLength(head);
        ListNode cur = dummy;
        for (int i = 1; i < length - n + 1; ++i) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
        ListNode ans = dummy.next;
        return ans;
    }

    private int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            ++length;
            head = head.next;
        }
        return length;
    }

环形链表

     * 给你一个链表的头节点 head ，判断链表中是否有环。
     * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
     * 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
     * 注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。
     * 如果链表中存在环，则返回 true 。 否则，返回 false 。
     *
     * 输入：head = [1,2], pos = 0
     * 输出：true
     * 解释：链表中有一个环，其尾部连接到第一个节点。
     
        public boolean hasCycle(ListNode head) {
            Set seen = new HashSet();
            while (head != null) {
                if (!seen.add(head)) {
                    return true;
                }
                head = head.next;
            }
            return false;
        }
        
         // 快慢指针
        public boolean hasCycle2(ListNode head) {
            if (head == null || head.next == null) {
                return false;
            }
            ListNode slow = head;
            ListNode fast = head.next;
            while (slow != fast) {
                if (fast == null || fast.next == null) {
                    return false;
                }
                slow = slow.next;
                fast = fast.next.next;
            }
            return true;
        }

环形链表2

* 给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回null。
* 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
* 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
* 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
* 不允许修改链表。
*
* 输入：head = [3,2,0,-4], pos = 1
* 输出：返回索引为 1 的链表节点
* 解释：链表中有一个环，其尾部连接到第二个节点。


 // hash
    public ListNode detectCycle(ListNode head) {
        ListNode pos = head;
        Set visited = new HashSet();
        while (pos != null) {
            if (visited.contains(pos)) {
                return pos;
            } else {
                visited.add(pos);
            }
            pos = pos.next;
        }
        return null;
    }

    // 快慢指针
    public ListNode detectCycle2(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode slow = head, fast = head;
        while (fast != null) {
            slow = slow.next;
            if (fast.next != null) {
                fast = fast.next.next;
            } else {
                return null;
            }
            if (fast == slow) {
                ListNode ptr = head;
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }

排序链表

* 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表
* 输入：head = [4,2,1,3]
* 输出：[1,2,3,4]


    public ListNode sortList(ListNode head) {
        return sortList(head, null);
    }

    // 自顶向下归并排序 找中点，分链表，排序合并
    public ListNode sortList(ListNode head, ListNode tail) {
        if (head == null) {
            return head;
        }
        if (head.next == tail) {
            head.next = null;
            return head;
        }
        //找到链表的中点，以中点为分界，将链表拆分成两个子链表
        //寻找链表的中点可以使用快慢指针的做法，快指针每次移动 22 步，慢指针每次移动 11 步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。
        ListNode slow = head, fast = head;
        while (fast != tail) {
            slow = slow.next;
            fast = fast.next;
            if (fast != tail) {
                fast = fast.next;
            }
        }
        ListNode mid = slow;
        // 对两个子链表分别排序
        ListNode list1 = sortList(head, mid);
        ListNode list2 = sortList(mid, tail);
        //将两个排序后的子链表合并，得到完整的排序后的链表
        ListNode sorted = merge(list1, list2);
        return sorted;
    }

    public ListNode merge(ListNode l1, ListNode l2) {
        // 哨兵节点 prehead
        ListNode prehead = new ListNode(-1);
        //prev 指针，调整它的next指针
        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                //l1 当前的节点接在 prev 节点的后面同时将 l1 指针往后移一位。
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = l1 == null ? l2 : l1;
        return prehead.next;
    }

反转链表

* 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
* 输入：head = [1,2,3,4,5]
* 输出：[5,4,3,2,1]

     * 在遍历链表时，将当前节点的next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。
     * 在更改引用之前，还需要存储后一个节点。最后返回新的头引用。
     
     
      public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

回文链表

* 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
* 输入：head = [1,2,2,1]
* 输出：true

    // 转换为数组进行双指针遍历
    public boolean isPalindrome(ListNode head) {
        List vals = new ArrayList();

        // 将链表的值复制到数组中
        ListNode currentNode = head;
        while (currentNode != null) {
            vals.add(currentNode.val);
            currentNode = currentNode.next;
        }

        // 使用双指针判断是否回文
        int front = 0;
        int back = vals.size() - 1;
        while (front < back) {
            if (!vals.get(front).equals(vals.get(back))) {
                return false;
            }
            front++;
            back--;
        }
        return true;
    }