描述 操作给定的二叉树，将其变换为源二叉树的镜像。 思路1：广度优先遍历 使用栈 使用栈进行层序遍历：从左往右加入，弹出的时候变成从右往左。再交换左右节点 8入栈 弹出8。将6和10入栈 交换6和10 弹出10。将9和11入栈 交换9和11 弹出6。将5和7入栈 交换5和7 public class Solution { public TreeNode Mirror (TreeNode pRoot) { if(pRoot == null) { return pRoot; } Stack<TreeNode...

描述 输入两棵二叉树A，B，判断B是不是A的子结构。（我们约定空树不是任意一个树的子结构） 假如给定A为{8,8,7,9,2,#,#,#,#,4,7}，B为{8,9,2}，2个树的结构如下，可以看出B是A的子结构 思路：递归 递归遍历大树的每个节点，和小树进行比较。时间复杂度O(MN)。M为A的节点数，N为B的节点数 public class Solution { public boolean HasSubtree(TreeNode root1,TreeNode root2) { if(root1 == null || root2 == null) { ...

描述 给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示。 思路1：递归+分治 前序遍历：根左右 中序遍历：左根右 前序遍历第一个元素为根节点，即1 在中序遍历序列中找到对应的元素1 此时左半部分为左子树{4,7,2}，对应的前序遍历序列为{2,4,7}。 右半部分为右子树{5,3,8,6}，对应的前序遍历序列为{3,5,6,8}。 用同样的方法找到左子树的根节点为2，右子树的根节点为3。分别作为1的子节点{1,2,3} 不...

描述 给定一棵结点数为n 二叉搜索树，请找出其中的第 k 小的TreeNode结点值。 返回第k小的节点值即可 不能查找的情况，如二叉树为空，则返回-1，或者k大于n等等，也返回-1 保证n个节点的值不一样 思路1：递归 二叉搜索树中序遍历可得升序数组 public class Solution { int i = 0; int ret = -1; public int KthNode (TreeNode proot, int k) { if(proot == null || k <= 0) { return -1; ...

描述 给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替） 思路1：队列层序遍历 public class Solution { public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) { ArrayList<ArrayList<Integer>> ret = new ArrayList<>(); if(pRoot == null) { return ret; ...

描述 输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度，根节点的深度视为 1 。 思路1：递归 public class Solution { public int TreeDepth(TreeNode root) { if(root == null) { return 0; } int l = TreeDepth(root.left); int r = TreeDepth(root.right); return ...

描述 在一个m*n的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？ 示例：输入二维数组， [ [1,3,1], [1,5,1], [4,2,1] ] 那么路径 1→3→5→2→1 可以拿到最多价值的礼物，价值为12 动态规划 dp[i][j]表示到grid[i-1][j-1]d的最大价值 dp[1][1]为1 dp[1][2]为1+3=4 dp[2][1]为1+1=2 dp[2][2]为1+3+5=9 状态转移...

描述 给定一个节点数为n的无序单链表，对其按升序排序。 思路1：辅助数组 遍历保存到数组中 对数组排序 重新构造链表 思路2：小顶堆 遍历构造小顶堆，遍历过程中 再一个一个取出，连接 public class Solution { public ListNode sortInList (ListNode head) { PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>((node1, node2)-> node1.val - node2.val); ...

描述 输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。 示例： 输入：[1,-2,3,10,-4,7,2,-5] 输出：18 思路1：暴力破解 计算所有子数组的和，保存最大值（会超时） public class Solution { public int FindGreatestSumOfSubArray(int[] array) { int ret = Integer.MIN_VALUE; for(int i = 0; i < array.length; i++) ...

描述 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。 数据范围：1<=n<=40 思路1：斐波那契数列 分治法：从上往下分治递归 假设n=5 最后一次可以跳1级，也可以跳2级，因此计算跳到第4级和第3级的路径之和即可：f(4)+f(3) public class Solution { public int jumpFloor(int target) { if(target == 1 || target == 2) { return target; ...

描述 思路1：双指针+交换 参考快排思想，i从前往后，j从后往前，找到不符合条件的值，进行交换 public class Solution { public int[] reOrderArrayTwo (int[] array) { int i = 0; int j = array.length - 1; while(i < j) { //i从前往后，找到第一个偶数 while(i < j && array[i] % 2 == 1) { ...

描述 思路1：数组排序+字符串比较 将int转为字符串 比较A和B的大小，当A+B<B+A时，则认为A<B。 使用Arrays.sort方法排序 public class Solution { public String PrintMinNumber(int [] numbers) { int len = numbers.length; String[] nums = new String[len]; for(int i = 0; i < len; i++) { nums[i] = numbe...

描述 输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序。(至少包括两个数) 示例： 输入：9 输出：[[2,3,4],[4,5]] 思路1：暴力破解 假设每个数都可能是连续序列的第一个数，计算每个连续区间 由于至少包括两个数，因此可以移动到sum/2即可，后面的序列一定大于sum，减少循环次数 public class Solution { public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) { ArrayLis...

描述 输入一个升序数组 array 和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，返回任意一组即可，如果无法找出这样的数字，返回一个空数组即可。 示例： 输入：[1,2,4,7,11,15],15 输出：[4,11] 思路1：两两组合 暴力破解，两两组合 public class Solution { public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) { ArrayList<Integer> list = new Array...