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
解:
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] 是对称的。
1plainplainplainplain
/
2 2
/ \ /
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1plainplainplain
/
2 2
\
3 3
进阶:
你可以运用递归和迭代两种方法解决这个问题吗?
解
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],
3plainplainplain
/
9 20
/
15 7
返回它的最大深度 3 。
解
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]
,
3
/ \
9 20
/ \
15 7
返回其自底向上的层次遍历为:
[
[15,7],
[9,20],
[3]
]
- 本文链接: https://wp.cmyr.ltd/archives/leetcode-practice-notes
- 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!
欢迎关注我的其它发布渠道
发表回复
要发表评论,您必须先登录。