数组删除（104 求二叉树的最大深度）

题目一、删除数组中的重复元素(简单)

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 各种元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

判题标准:

系统会用下面的代码来测试你的题解:

int[] nums = [...]; // 输入数组int[] expectedNums = [...]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;for (int i = 0; i < k; i++) {assert nums[i] == expectedNums[i];}如果所有断言都通过，那么您的题解将被 通过。

示例 1：

输入：nums = [1,1,2]输出：2, nums = [1,2,_]解释：函数应该返回新的长度 2 ，并且原数组 nums 前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。示例 2：

输入：nums = [0,0,1,1,1,2,2,3,3,4]输出：5, nums = [0,1,2,3,4]解释：函数应该返回新的长度 5 ， 并且原数组 nums 前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

分析题意

根据题意，要去除数组中的重复元素，我们可能第一想到的是找到重复项，然后把所有的重复项遍历删除就可以了，但是出题人想要我们细读题意: 1) 数组是升序的, 2) 元素只要在数组中出现一次就能满足条件，3) 最后的返回结果和数组的实际长度可以不相同，比如删除重复项后有5个元素，实际数组中也7个元素也算通过的，只要把5个不重复的元素放到数组前面也可算通过。

我的解题思路

设置一个初始化的变量为index, 默认值为0， index用来记录重复元素重新赋值在数组中的位置。当数据发生变化时，那么发生变化的位置是i 对应的赋值给index, 同时需要index向后移一位，index的值每加1表示不重复元素+1一个，因此最后返回的index即为不重复元素的个数。

public int removeDuplicates(int[] nums) { int t = 0; for (int i = 0; i < nums.length; i++) { if (i == 0 || nums[i] != nums[i - 1]) { nums[t++] = nums[i]; } } return t; }

执行结果:

官方方案

快慢指针法， 用2个指针分别为fast和slow分别赋值为1，指向第一个位置，fast指针每次移动一位。当fast与fast-1指向的元素不相同时，那么slow指针向右移动一位，同时将nums[fast]赋值给nums[slow]。

public int removeDuplicates1(int[] nums) { int n = nums.length; if (n == 0) { return 0; } int fast = 1; int slow = 1; while (fast < n) { if (nums[fast] != nums[fast - 1]) { nums[slow] = nums[fast]; ++slow; } ++fast; } System.out.println(Arrays.toString(nums)); return slow; }

题目二、求二叉树的最大深度(简单)

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：给定二叉树 [3,9,20,null,null,15,7]，

3/ 9 20/ 15 7返回它的最大深度 3 。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的解题思路

要求树的深度，我的脑海里的第一印象浮现出来的是广度优先算法和深度优先算法，求解深度比较适合用深度优先算法，因为该算法采用中左右的思想，先从左子树遍历到树的最深处，然后再切换到右子树。

发现用深度优先算法可以遍历出整个树: 先用一个栈，将root节点放入到栈里，然后再看root的左子树和右子树为不为空，右子树不为空，那么先让右子树进栈，然后再左子树，因为栈的特性是先进后出，因此每次需要右先进才能达到左子树先遍历得到的结果。

private static List DepthTraverse(TreeNode head) { List<Integer> results = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); stack.add(head); while (!stack.isEmpty()) { TreeNode<Integer> node = stack.pop(); results.add(node.getData()); if (node.right != null) { stack.add(node.right); } if (node.left != null) { stack.add(node.left); } } return results; }

但是我还是不好去计算深度，然后我就暂时放弃了，采用另外一种思路，递归可以不可以实现?

根据二叉树的特性，每个节点最多只有2个节点，并且左子树和右子树均可能为空，因此我们可以想象一下，可以把一个二叉树当做一个小二叉树不断迭代生成的一个大二叉树。

比如上图，我们可以把2, null, 3当做一个二叉树，然后再把2,null,3当做1的左子树。

我们只需要将每次的左子树右子树计算的递归当做一层深度+1, 每次递归取左子树和右子树中最大值+1即可。

public int maxDepth(TreeNode root) { return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1; }

看了一下官方的题解，思路和我写的一样，推荐使用递归解法。