vlambda博客
学习文章列表

104. 二叉树的最大深度

力扣题目链接^[1]

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

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

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

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

  3
 / \
9  20
  /   \
  15   7

返回它的最大深度 3 。

思路：

本题可采用递归的思路进行题解。要求出二叉树的最大深度，可以求出左右子树的最大深度，找到较大者并且加一便是二叉树本身的最大深度。递归终止条件是：如果当前节点为空，则返回0，没有节点说明深度为0。

递归

/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    if (!root) return 0;
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
};

总结

本题是递归的经典应用。需要注意终止递归的条件。

645. 错误的集合

力扣题目链接^[2]

集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。

给定一个数组 nums 代表了集合 S 发生错误后的结果。

请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。

「示例 1：」

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

「提示：」

• 2 <= nums.length <= 10^4
• 1 <= nums[i] <= 10^4

思路：

最容易想到的是使用哈希表存储所有的元素。由于元素范围是[1, n]，因此循环1~n，判断当前元素是否存在于哈希表中，如果存在且重复，则是结果数组的第一项，如果不存在，则是结果数组的第二项。

哈希表

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findErrorNums = function(nums) {
    let map = new Map();
    let length = nums.length;
    let res = [];
    for (const num of nums) {
        map.set(num, map.has(num) ? 2 : 1);
    }
    for (let i = 1; i <= length; i++) {
        const count = map.get(i) || 0;
        if (count === 2) res[0] = i;
        if (count === 0) res[1] = i;
    }
    return res;
};

总结

代码的核心逻辑是：第一次遍历数组，将重复元素的哈希值设置为2，不重复的设置为1。第二次遍历来找到未曾出现的元素，以及重复的元素。未曾出现的元素不存在于哈希表，因此可以赋值默认值0。重复的元素哈希值是2，赋值计数变量为2。最后将重复的元素赋值给结果数组第一项，将缺失的元素赋值给结果数组第二项。返回结果数组即可。

参考资料