二叉树相关的算法题

目录

1. 📝 算法题汇总
2. 简单难度
3. **1. 对称二叉树（**LeetCode 101）
4. **2. 二叉树的最大深度（**LeetCode 104）
5. **3. 翻转二叉树（**LeetCode 226）
6. **4. 路径总和（**LeetCode 112）
7. **5. 左叶子之和（**LeetCode 404）
8. 中等难度
9. **1. 二叉树的层序遍历（**LeetCode 102）
10. **2. 从中序与后序遍历构造二叉树（**LeetCode 106）
11. **3. 不同的二叉搜索树（**LeetCode 96）
12. **4. 组合总和Ⅱ（**LeetCode 40）
13. **5. 二叉树的所有路径（**LeetCode 257）
14. **6. 修剪二叉搜索树（**LeetCode 669）
15. 困难难度
16. **1. 二叉树中的最大路径和（**LeetCode 124）
17. **2. 二叉树的序列化与反序列化（**LeetCode 297）
18. **3. 监控二叉树（**LeetCode 968）
19. **4. 合并二叉树（**LeetCode 617）扩展问题
20. 解题代码

📝 算法题汇总#

---

简单难度#

**1. 对称二叉树（**LeetCode 101）#

• 检查二叉树是否镜像对称，递归法比较左右子树，或迭代法用队列/栈逐层对比。
• 解题代码

**2. 二叉树的最大深度（**LeetCode 104）#

• 递归法返回左右子树最大深度+1，或层序遍历统计层数。
• 解题代码

**3. 翻转二叉树（**LeetCode 226）#

• 递归交换左右子树，或迭代法逐层处理节点。

**4. 路径总和（**LeetCode 112）#

• 判断是否存在根到叶子的路径和等于目标值，递归或DFS回溯。

**5. 左叶子之和（**LeetCode 404）#

• 遍历时判断左子节点是否为叶子节点，累计值。

---

中等难度#

**1. 二叉树的层序遍历（**LeetCode 102）#

• 队列实现BFS，按层输出节点值。

**2. 从中序与后序遍历构造二叉树（**LeetCode 106）#

• 递归分割中序和后序数组，确定根节点及左右子树范围。

**3. 不同的二叉搜索树（**LeetCode 96）#

• 动态规划：dp[i]表示i个节点的二叉搜索树数量，状态转移为左子树与右子树的组合。

**4. 组合总和Ⅱ（**LeetCode 40）#

• 回溯法结合树层去重，避免重复组合。

**5. 二叉树的所有路径（**LeetCode 257）#

• 回溯法记录路径，注意递归与回溯的配合。

**6. 修剪二叉搜索树（**LeetCode 669）#

• 递归调整子树，保留符合范围的节点。

---

困难难度#

**1. 二叉树中的最大路径和（**LeetCode 124）#

• 后序遍历计算子树贡献值，维护全局最大值（需结合LeetCode标准题库，搜索结果未直接提及但属于经典难题）。

**2. 二叉树的序列化与反序列化（**LeetCode 297）#

• 设计前序/层序遍历的序列化格式，处理空节点标记。

**3. 监控二叉树（**LeetCode 968）#

• 贪心+状态机，覆盖所有节点所需最小摄像头数（需结合LeetCode题库）。

**4. 合并二叉树（**LeetCode 617）扩展问题#

• 若涉及复杂合并逻辑（如动态调整结构），可能提升为困难题。

---

解题代码#

**对称二叉树（**LeetCode 101）

• 方法一: 递归

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def is_symmetric1(root) -> bool:
    """
    对称二叉树（LeetCode 101）
    给你一个二叉树的根节点 root ， 检查它是否轴对称。
    递归实现
    :param root:
    :return:
    """

    if not root:
        return False

    def is_mirror(left, right):
        if not left and not right:
            return True
        if not left or not right:
            return False
        return (left.val == right.val) and is_mirror(left.left, right.right) and is_mirror(left.right, right.left)

    return is_mirror(root.left, root.right)

• 方法二: 迭代

def is_symmetric2(root) -> bool:
    """
    对称二叉树（LeetCode 101）
    给你一个二叉树的根节点 root ， 检查它是否轴对称。
    迭代实现
    :param root:
    :return:
    """

    if not root:
        return False

    queue = [root.left, root.right]
    while queue:
        left = queue.pop(0)
        right = queue.pop(0)
        if not left and not right:
            continue
        if not left or not right:
            return False
        if left.val != right.val:
            return False
        queue.append(left.left)
        queue.append(right.right)
        queue.append(left.right)
        queue.append(right.left)

    return True

• 测试用例:

# 测试用例1：对称树
#     1
#    / \
#   2   2
#  / \ / \
# 3  4 4 3
root1 = TreeNode(1,
                TreeNode(2, TreeNode(3), TreeNode(4)),
                TreeNode(2, TreeNode(4), TreeNode(3)))
print(isSymmetric(root1))  # 输出 True

# 测试用例2：非对称树
#     1
#    / \
#   2   2
#    \   \
#     3   3
root2 = TreeNode(1,
                TreeNode(2, None, TreeNode(3)),
                TreeNode(2, None, TreeNode(3)))
print(isSymmetric(root2))  # 输出 False