二叉树经典题目：相同、对称与层序遍历深度解析

最近在 LeetCode 刷题，二叉树的这几个经典题目：100. 相同的树、101. 对称二叉树、102. 二叉树的层序遍历，感觉很有代表性，涵盖了二叉树的基础遍历思想和递归技巧。很多同学在面试中也经常遇到类似的问题，本文将深入剖析这三个问题，并分享一些实战避坑经验。

1. 相同的树 (100. 相同的树)

问题场景重现

给定两个二叉树的根节点 p 和 q，编写一个函数来检验这两棵树是否相同。如果两棵树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

底层原理深度剖析

判断两棵树是否相同，本质上是一个递归比较的过程。我们需要同时遍历两棵树，比较对应节点的值。如果遇到以下情况，则判定为不相同：

• 其中一棵树为空，另一棵树不为空
• 两棵树都非空，但对应节点的值不相等

代码解决方案

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

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q:
            return True # 两棵树都为空，相同
        if not p or not q:
            return False # 其中一棵树为空，另一棵树不为空，不同
        if p.val != q.val:
            return False # 节点值不相等，不同
        # 递归比较左子树和右子树
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

实战避坑经验总结

• 递归的终止条件一定要明确，避免无限递归导致栈溢出。
• 注意 and 和 or 的优先级，确保逻辑正确。

2. 对称二叉树 (101. 对称二叉树)

问题场景重现

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

底层原理深度剖析

判断一棵树是否对称，可以将其转化为判断两棵树是否“镜像相同”。 我们可以将树的左子树和右子树看作是两棵独立的树，然后比较它们的结构和节点值是否对称。

代码解决方案

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        def isMirror(p: TreeNode, q: TreeNode) -> bool:
            if not p and not q:
                return True
            if not p or not q:
                return False
            return (p.val == q.val) and isMirror(p.left, q.right) and isMirror(p.right, q.left)

        return isMirror(root.left, root.right)

实战避坑经验总结

• 将问题分解为“判断两棵树是否镜像对称”的子问题，降低难度。
• 递归时，注意左右子树的对应关系。

3. 二叉树的层序遍历 (102. 二叉树的层序遍历)

问题场景重现

给你一个二叉树，请你返回其按层序遍历得到的节点值。（即逐层地，从左到右访问所有节点）。

底层原理深度剖析

层序遍历通常使用队列来实现。首先将根节点入队，然后循环从队列中取出节点，访问该节点，并将其左右子节点（如果存在）入队。 这样，队列中的节点就按照层序排列。

代码解决方案

from collections import deque

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []

        queue = deque([root])
        result = []

        while queue:
            level_size = len(queue)
            level_nodes = []
            for _ in range(level_size):
                node = queue.popleft()
                level_nodes.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(level_nodes)

        return result

实战避坑经验总结

• 使用 collections.deque 作为队列，效率更高。
• 在每一层遍历开始前，记录队列的长度，作为该层节点的数量。这样可以正确地将节点分层。
• 可以结合 Nginx 的 upstream 模块来理解， Nginx 将请求按照某种规则（如轮询）分发到后端服务器（可以理解为二叉树的子节点）。 Nginx 通过配置反向代理和负载均衡，实现高可用和高并发，而层序遍历则提供了一种有效的节点组织方式。实际应用中，我们可以使用宝塔面板简化 Nginx 的配置，并且监控并发连接数等关键指标。

总结

LeetCode 刷题不仅仅是为了应付面试，更是提升编程能力和算法思维的重要途径。 掌握这些二叉树的基础题目，可以为解决更复杂的问题打下坚实的基础。