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]
]