「每日LeetCode」2020年9月5日

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

Lt101.对称二叉树、Lt107.二叉树的层次遍历 II、Lt108.将有序数组转换为二叉搜索树

101.对称二叉树

Category Difficulty Likes Dislikes
algorithms Easy (52.90%) 998 -

Tags
tree | depth-first-search | breadth-first-search
Companies
bloomberg | linkedin | microsoft
给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

1
2
3
4
5
1
   / \
  2   2
 / \ / \
3  4 4  3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

1
2
3
4
5
1
   / \
  2   2
   \   \
   3    3

进阶：
你可以运用递归和迭代两种方法解决这个问题吗？

Discussion | Solution

思路

和 101.相同的树类似，递归中传的参数分别取左右节点进行判断即可。

解答

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
/*
 * @lc app=leetcode.cn id=101 lang=javascript
 *
 * [101] 对称二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function (root) {
  if (!root) return true;
  return visit(root.left, root.right);
};

const visit = (q, p) => {
  if (!p && !q) return true;
  if ((p && !q) || (q && !p)) return false;
  return p.val === q.val && visit(p.left, q.right) && visit(p.right, q.left);
};
// @lc code=end
1
2
3
4
Accepted
195/195 cases passed (96 ms)
Your runtime beats 40.76 % of javascript submissions
Your memory usage beats 5.05 % of javascript submissions (40.2 MB)

107.二叉树的层次遍历 II

Category Difficulty Likes Dislikes
algorithms Easy (66.42%) 296 -

Tags
tree | breadth-first-search
Companies
Unknown
给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
例如：
给定二叉树 [3,9,20,null,null,15,7],

1
2
3
4
5
3
   / \
  9  20
    /  \
   15   7

返回其自底向上的层次遍历为：

1
2
3
4
5
[
  [15,7],
  [9,20],
  [3]
]

Discussion | Solution

思路

广度优先遍历。先将根节点放入栈中。创建一个临时栈和临时结果数组，遍历当前栈中的所有节点，如果存在左节点或右节点，将遍历节点的左节点和右节点加入临时栈中，同时将遍历节点的值加入临时结果数组中。遍历结束以后，在结果数组添加到临时结果数组的第一个。将临时栈的内容赋给栈，继续遍历下一层的节点，直到遍历完树。

解答

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
/*
 * @lc app=leetcode.cn id=107 lang=javascript
 *
 * [107] 二叉树的层次遍历 II
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrderBottom = function (root) {
  if (!root) return [];
  let stack = [];
  const res = [];
  stack.push(root);
  while (stack.length) {
    let tempStack = [];
    let tempRes = [];
    while (stack.length) {
      let node = stack.shift();
      tempRes.push(node.val);
      if (node.left) tempStack.push(node.left);
      if (node.right) tempStack.push(node.right);
    }
    if (tempRes.length) res.unshift(tempRes);
    stack = stack.concat(tempStack);
  }
  return res;
};
// @lc code=end
1
2
3
4
Accepted
34/34 cases passed (92 ms)
Your runtime beats 42.2 % of javascript submissions
Your memory usage beats 5.95 % of javascript submissions (40 MB)

108.将有序数组转换为二叉搜索树

Category Difficulty Likes Dislikes
algorithms Easy (74.07%) 572 -

Tags
tree | depth-first-search
Companies
airbnb
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点  *的左右两个子树的高度差的绝对值不超过 1。
*示例:**

1
2
3
4
5
6
7
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
      0
     / \
   -3   9
   /   /
 -10  5

Discussion | Solution

思路

只有有序数组才可使用二分法，重点是点的选取总是左右剩下数组的中点，使用递归反复添加节点即可。

解答

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
/*
 * @lc app=leetcode.cn id=108 lang=javascript
 *
 * [108] 将有序数组转换为二叉搜索树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function (nums) {
  if (!nums.length) return null;
  const mid = parseInt(nums.length / 2);
  const node = new TreeNode(nums[mid]);
  node.left = sortedArrayToBST(nums.slice(0, mid));
  node.right = sortedArrayToBST(nums.slice(mid + 1));
  return node;
};
// @lc code=end
1
2
3
4
Accepted
32/32 cases passed (100 ms)
Your runtime beats 34.03 % of javascript submissions
Your memory usage beats 9.86 % of javascript submissions (43.2 MB)