在计算机编程的世界里，二叉树相关的问题一直是面试中的高频考点。今天，咱们就来聊聊几个常见的二叉树面试题：对称二叉树、二叉树的最大深度以及路径总和问题。
一、对称二叉树
1. 问题描述
啥是对称二叉树呢？简单来说，就是一棵二叉树从中间“劈开”，左右两边就像照镜子一样，是对称的。比如说，根节点的左子树和右子树得长得一模一样，而且对应位置的节点值也得相等。
2. 示例代码（Python）
# 定义二叉树节点类
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def isSymmetric(root):
def isMirror(t1, t2):
# 如果两个节点都为空，说明这部分是对称的
if not t1 and not t2:
return True
# 如果其中一个节点为空，另一个不为空，那就不对称了
if not t1 or not t2:
return False
# 节点值相等，并且左子树的左节点和右子树的右节点对称，左子树的右节点和右子树的左节点对称
return t1.val == t2.val and isMirror(t1.left, t2.right) and isMirror(t1.right, t2.left)
return isMirror(root, root)
# 示例使用
# 构建一个对称二叉树
# 1
# / \
# 2 2
# / \ / \
# 3 4 4 3
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(2)
root.left.left = TreeNode(3)
root.left.right = TreeNode(4)
root.right.left = TreeNode(4)
root.right.right = TreeNode(3)
print(isSymmetric(root)) # 输出: True
3. 应用场景
对称二叉树的判断在很多场景都有用，比如在图像处理中，判断一个图形是否左右对称；在数据结构的设计中，检查某些树形结构是否具有对称性质，方便后续的操作和处理。
4. 技术优缺点
优点：代码逻辑相对清晰，递归的方法实现起来比较简洁，容易理解。缺点：递归调用会占用一定的栈空间，如果树的深度很大，可能会导致栈溢出。
5. 注意事项
在使用递归方法时，要注意递归的终止条件，避免无限递归。同时，对于节点的空值判断要准确，防止出现空指针异常。
二、二叉树的最大深度
1. 问题描述
二叉树的最大深度就是从根节点到最远叶子节点的最长路径上的节点数。比如说，只有一个根节点的二叉树，它的最大深度就是 1 ；如果根节点下面还有左右子树，那就要看左右子树的深度，取最大值再加上根节点这一层，就是整个树的最大深度。
2. 示例代码（Python）
# 定义二叉树节点类
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def maxDepth(root):
if not root:
return 0
# 递归计算左子树的深度
left_depth = maxDepth(root.left)
# 递归计算右子树的深度
right_depth = maxDepth(root.right)
# 取左右子树深度的最大值，再加上根节点这一层
return max(left_depth, right_depth) + 1
# 示例使用
# 构建一个二叉树
# 1
# / \
# 2 3
# / \
# 4 5
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(maxDepth(root)) # 输出: 3
3. 应用场景
在很多需要对树形结构进行分层处理的场景中，都需要知道二叉树的最大深度。比如在数据库的索引树中，了解树的最大深度可以评估索引的查找效率；在游戏开发中，对于树形的关卡结构，知道最大深度可以合理安排关卡的难度和数量。
4. 技术优缺点
优点：递归实现简单直观，代码量少。缺点：和对称二叉树的递归实现一样，递归调用会占用栈空间，对于深度很大的树可能会有栈溢出的风险。
5. 注意事项
同样要注意递归的终止条件，当节点为空时，深度为 0。在计算左右子树深度时，要确保递归调用的正确性。
三、路径总和问题
1. 问题描述
路径总和问题就是判断在二叉树中是否存在一条从根节点到叶子节点的路径，使得这条路径上所有节点的值之和等于给定的目标值。比如说，给定一个目标值 10，在二叉树中找一条路径，路径上节点值相加等于 10 ，如果能找到，就返回 True ，找不到就返回 False 。
2. 示例代码（Python）
# 定义二叉树节点类
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def hasPathSum(root, targetSum):
if not root:
return False
# 减去当前节点的值
targetSum -= root.val
# 如果是叶子节点，并且剩余的目标值为 0，说明找到了满足条件的路径
if not root.left and not root.right:
return targetSum == 0
# 递归检查左子树和右子树
return hasPathSum(root.left, targetSum) or hasPathSum(root.right, targetSum)
# 示例使用
# 构建一个二叉树
# 5
# / \
# 4 8
# / / \
# 11 13 4
# / \ \
# 7 2 1
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left.left = TreeNode(11)
root.left.left.left = TreeNode(7)
root.left.left.right = TreeNode(2)
root.right.left = TreeNode(13)
root.right.right = TreeNode(4)
root.right.right.right = TreeNode(1)
targetSum = 22
print(hasPathSum(root, targetSum)) # 输出: True
3. 应用场景
路径总和问题在很多实际场景中都有应用。比如在财务系统中，判断一系列账目记录是否能达到某个预算额度；在物流系统中，判断从起点到终点的一系列运输费用之和是否在预算范围内。
4. 技术优缺点
优点：递归的方式简洁明了，能够快速实现功能。缺点：递归调用的性能问题依然存在，对于大规模的二叉树可能效率不高。
5. 注意事项
在递归过程中，要注意更新目标值，每次减去当前节点的值。对于叶子节点的判断要准确，确保路径是从根节点到叶子节点的完整路径。
四、总结
通过对对称二叉树、二叉树的最大深度和路径总和问题的分析和代码实现，我们可以看到，这些问题虽然都围绕着二叉树展开，但各自有不同的应用场景和解决思路。在解决这些问题时，递归是一种常用且有效的方法，但要注意递归可能带来的性能问题，比如栈溢出。在实际编程中，我们可以根据具体情况选择合适的算法和数据结构，同时要注意边界条件和异常处理，保证代码的正确性和健壮性。
评论