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

解：

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://blog.cmyr.ltd/archives/d1c8c8d3.html
版权声明：本文采用 CC BY-NC-SA 4.0 协议 进行分发，转载请注明出处！