「每日LeetCode」2020年9月10日

本文最后更新于：2023年3月19日 晚上

Lt606.根据二叉树创建字符串、Lt617.合并二叉树、Lt645.错误的集合

606.根据二叉树创建字符串

Category Difficulty Likes Dislikes
algorithms Easy (54.64%) 143 -

Tags
string | tree
Companies
amazon
你需要采用前序遍历的方式，将一个二叉树转换成一个由括号和整数组成的字符串。
空节点则用一对空括号 “()” 表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
示例 1:

1
2
3
4
5
6
7
8
9
10
输入: 二叉树: [1,2,3,4]
       1
     /   \
    2     3
   /
  4
输出: "1(2(4))(3)"
解释: 原本将是“1(2(4)())(3())”，
在你省略所有不必要的空括号对之后，
它将是“1(2(4))(3)”。

示例 2:

1
2
3
4
5
6
7
8
9
输入: 二叉树: [1,2,3,null,4]
       1
     /   \
    2     3
     \
      4
输出: "1(2()(4))(3)"
解释: 和第一个示例相似，
除了我们不能省略第一个对括号来中断输入和输出之间的一对一映射关系。

Discussion | Solution

思路

先序遍历，如果只有左节点，返回 val(left)。如果只有右节点，返回 val()(right)。如果有左节点和右节点，返回 val(left)(right)，如果没有节点值返回 val。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/*
 * @lc app=leetcode.cn id=606 lang=javascript
 *
 * [606] 根据二叉树创建字符串
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} t
 * @return {string}
 */
var tree2str = function (t) {
  return visit(t);
};

const visit = (node) => {
  if (node) {
    let str = "";
    if (!node.left && !node.right) {
      return node.val + "";
    } else if (node.left && !node.right) {
      str = `${node.val}(${visit(node.left)})`;
    } else if (!node.left && node.right) {
      str = `${node.val}()(${visit(node.right)})`;
    } else {
      str = `${node.val}(${visit(node.left)})(${visit(node.right)})`;
    }
    return str;
  } else {
    return "";
  }
};
// @lc code=end
1
2
3
4
Accepted
162/162 cases passed (108 ms)
Your runtime beats 25 % of javascript submissions
Your memory usage beats 70 % of javascript submissions (42.7 MB)

617.合并二叉树

Category Difficulty Likes Dislikes
algorithms Easy (77.20%) 462 -

Tags
tree
Companies
amazon
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为  **NULL 的节点将直接作为新二叉树的节点。
**示例  1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入:
	Tree 1                     Tree 2
          1                         2
         / \                       / \
        3   2                     1   3
       /                           \   \
      5                             4   7
输出:
合并后的树:
	     3
	    / \
	   4   5
	  / \   \
	 5   4   7

注意: 合并必须从两个树的根节点开始。

Discussion | Solution

思路

当 t1，t2 都存在时，将 t1 的值加上 t2 的值赋值给 t1。然后对 t1 的左右节点递归计算。当 t1 和 t2 有一个不存在或都不存在时，返回另一个边余下的节点，余下的一边不需要进行计算。当到根节点时直接返回已经加上 t2 的 t1，所以 t1 应该放在 || 前面。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/*
 * @lc app=leetcode.cn id=617 lang=javascript
 *
 * [617] 合并二叉树
 */

const { VisitorKeys } = require("estraverse");

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} t1
 * @param {TreeNode} t2
 * @return {TreeNode}
 */
var mergeTrees = function (t1, t2) {
  if (t1 && t2) {
    t1.val += t2.val;
    t1.left = mergeTrees(t1.left, t2.left);
    t1.right = mergeTrees(t1.right, t2.right);
  }
  return t1 || t2;
};

// @lc code=end
1
2
3
4
Accepted
183/183 cases passed (136 ms)
Your runtime beats 27.42 % of javascript submissions
Your memory usage beats 21.84 % of javascript submissions (45.8 MB)

645.错误的集合

Category Difficulty Likes Dislikes
algorithms Easy (42.30%) 121 -

Tags
hash-table | math
Companies
amazon
集合 S 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个元素复制了成了集合里面的另外一个元素的值，导致集合丢失了一个整数并且有一个元素重复。
给定一个数组 nums 代表了集合 S 发生错误后的结果。你的任务是首先寻找到重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。
示例 1:

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

注意:

  1. 给定数组的长度范围是  [2, 10000]。
  2. 给定的数组是无序的。

Discussion | Solution

思路

遍历数组，用 map 判断是否出现过，出现过添加到结果数组中。
对数组排序，如果当前元素不等于下标+1，数组中添加下标+1 的值。
如果遍历完都没有查到，则缺少的是最后一个数，同 nums 的长度。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/*
 * @lc app=leetcode.cn id=645 lang=javascript
 *
 * [645] 错误的集合
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findErrorNums = function (nums) {
  const map = new Map();
  const res = [];
  for (const num of nums) {
    if (map.get(num)) {
      res.push(num);
    } else {
      map.set(num, map.get(num) ? map.get(num) + 1 : 1);
    }
  }
  const sortArr = [...map.keys()].sort((a, b) => Number(a) - Number(b));
  if (
    !sortArr.some((e, index) => {
      if (e !== index + 1) {
        res.push(index + 1);
        return true;
      }
    })
  ) {
    res.push(nums.length);
  }
  return res;
};
// @lc code=end
1
2
3
4
Accepted
49/49 cases passed (156 ms)
Your runtime beats 20.44 % of javascript submissions
Your memory usage beats 5.4 % of javascript submissions (48.9 MB)