「每日LeetCode」2020年9月4日

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

Lt226.翻转二叉树、Lt100.相同的树、Lt104.二叉树的最大深度、Lt111.二叉树的最小深度

226.翻转二叉树

Category Difficulty Likes Dislikes
algorithms Easy (76.37%) 557 -

Tags
tree
Companies
Unknown
翻转一棵二叉树。
示例：
输入：

1
2
3
4
5
		 4
   /   \
  2     7
 / \   / \
1   3 6   9

输出：

1
2
3
4
5
		 4
   /   \
  7     2
 / \   / \
9   6 3   1

备注:
这个问题是受到 Max Howell 的 原问题 启发的 ：
谷歌：我们 90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。

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
39
/*
 * @lc app=leetcode.cn id=226 lang=javascript
 *
 * [226] 翻转二叉树
 */

const { reverse } = require("core-js/fn/array");

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

const visit = (node) => {
  if (!node) return null;
  reverse(node);
  visit(node.left);
  visit(node.right);
};

const reverse = (node) => {
  let tmp = node.left;
  node.left = node.right;
  node.right = tmp;
};

// @lc code=end
1
2
3
4
Accepted
68/68 cases passed (96 ms)
Your runtime beats 11.62 % of javascript submissions
Your memory usage beats 5.42 % of javascript submissions (38.3 MB)

100.相同的树

Category Difficulty Likes Dislikes
algorithms Easy (60.13%) 463 -

Tags
tree | depth-first-search
Companies
bloomberg
给定两个二叉树，编写一个函数来检验它们是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例  1:

1
2
3
4
5
输入:       1         1
          / \       / \
         2   3     2   3
        [1,2,3],   [1,2,3]
输出: true

示例 2:

1
2
3
4
5
输入:      1          1
          /           \
         2             2
        [1,2],     [1,null,2]
输出: false

示例  3:

1
2
3
4
5
输入:       1         1
          / \       / \
         2   1     1   2
        [1,2,1],   [1,1,2]
输出: false

Discussion | Solution

思路

按照递归的思想来进行深度遍历。如果两个节点都没有子节点则返回 true，如果两个节点其中一个不为空则返回 false，若两个节点都不为空，就轮流再比较左右节点。

解答

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
/*
 * @lc app=leetcode.cn id=100 lang=javascript
 *
 * [100] 相同的树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function (p, q) {
  if (!p && !q) return true;
  else if (!p || !q) return false;
  return (
    p.val === q.val &&
    isSameTree(p.left, q.left) &&
    isSameTree(p.right, q.right)
  );
};
// @lc code=end
1
2
3
4
Accepted
59/59 cases passed (68 ms)
Your runtime beats 94 % of javascript submissions
Your memory usage beats 27.28 % of javascript submissions (38 MB)

104.二叉树的最大深度

Category Difficulty Likes Dislikes
algorithms Easy (74.96%) 688 -

Tags
tree | depth-first-search
Companies
apple | linkedin | uber | yahoo
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，

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

返回它的最大深度  3 。

Discussion | Solution

思路

对一个点来说，深度为左节点深度和右节点深度的最大值+1，如果这个点是叶子节点，则深度不再增加，返回 0

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
 * @lc app=leetcode.cn id=104 lang=javascript
 *
 * [104] 二叉树的最大深度
 */

// @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 maxDepth = function (root) {
  return root ? Math.max(maxDepth(root.left), maxDepth(root.right)) + 1 : 0;
};

// @lc code=end
1
2
3
4
Accepted
39/39 cases passed (92 ms)
Your runtime beats 60.28 % of javascript submissions
Your memory usage beats 20.88 % of javascript submissions (40.8 MB)

111.二叉树的最小深度

Category Difficulty Likes Dislikes
algorithms Easy (44.32%) 358 -

Tags
tree | depth-first-search | breadth-first-search
Companies
Unknown
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],

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

返回它的最小深度  2.

Discussion | Solution

思路

对一个点来说，如果他有左节点和右节点，求最小深度，取两边节点深度小的那一个加一。如果他只有左节点或者右节点，取他左节点或者右节点的深度再加一。如果他没有左右节点，返回 1。

解答

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
/*
 * @lc app=leetcode.cn id=111 lang=javascript
 *
 * [111] 二叉树的最小深度
 */

// @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 minDepth = function (root) {
  if (root) {
    if (!root.left && root.right) {
      return minDepth(root.right) + 1;
    } else if (root.left && !root.right) {
      return minDepth(root.left) + 1;
    } else {
      return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
    }
  } else {
    return 0;
  }
};
// @lc code=end
1
2
3
4
Accepted
41/41 cases passed (92 ms)
Your runtime beats 67.92 % of javascript submissions
Your memory usage beats 64.71 % of javascript submissions (42 MB)