0%

2020-08-22 LeetCode练习笔记

LeetCode练习笔记

100. 相同的树

难度:简单

给定两个二叉树,编写一个函数来检验它们是否相同。

如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。

示例 1:

输入: 1 1
/ \ /
2 3 2 3

    [1,2,3],   [1,2,3]

输出: true
示例 2:

输入: 1 1
/
2 2

    [1,2],     [1,null,2]

输出: false
示例 3:

输入: 1 1
/ \ /
2 1 1 2

    [1,2,1],   [1,1,2]

输出: false

解:

1
2
3
4
5
6
7
8
9
10
11
12
function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
if (!p && !q) { // 若两者同时为空则为真
return true
}
if (!p || !q) { //若两者不同时为空则为假
return false
}
if (p.val !== q.val) { // 若两者值不相等则为假
return false
}
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right) // 递归左右子树
}

101. 对称二叉树

难度:简单

给定一个二叉树,检查它是否是镜像对称的。

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

1

/
2 2
/ \ /
3 4 4 3

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

1

/
2 2
\
3 3

进阶:

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

1
2
3
4
5
6
7
8
9
10
11
12
function isSymmetric(root: TreeNode | null): boolean {
return root ? fun(root.left, root.right) : true
}
function fun(r1: TreeNode | null, r2: TreeNode | null): boolean {
if (r1 === r2) {
return true
}
if (r1 && r2 && r1.val === r2.val) {
return fun(r1.left, r2.right) && fun(r1.right, r2.left)
}
return false
}

104. 二叉树的最大深度

难度:简单

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

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

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

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

3

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

1
2
3
4
5
6
7
8
9
function maxDepth(root: TreeNode | null): number {
if (!root) {
return 0
}
if (!root.left && !root.right) {
return 1
}
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right))
}

107. 二叉树的层次遍历 II

难度:简单

给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)

例如:
给定二叉树 [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]
]

本文作者:草梅友仁
本文地址: https://blog.cmyr.ltd/archives/d1c8c8d3.html
版权声明:转载请注明出处!

坚持原创技术分享,您的支持将鼓励我继续创作!