1. 二叉树基础与遍历方法二叉树是每个节点最多有两个子节点的树结构在算法面试和工程实践中极为常见。理解它的基本性质是解决所有二叉树问题的前提。二叉树的节点通常定义为包含值、左子节点和右子节点的结构体用代码表示如下class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right二叉树的遍历方式主要有四种每种都有其特定的应用场景前序遍历根节点 → 左子树 → 右子树。适合需要先处理根节点信息的场景比如树的序列化。中序遍历左子树 → 根节点 → 右子树。对二叉搜索树会得到有序序列。后序遍历左子树 → 右子树 → 根节点。适合先处理子节点再处理父节点的场景如计算子树属性。层序遍历按层级从上到下、从左到右遍历。适合需要按层级分析的场景。递归实现前序遍历的代码示例def preorder(root): if not root: return print(root.val) # 处理当前节点 preorder(root.left) # 递归左子树 preorder(root.right) # 递归右子树在实际工程中递归虽然简洁但可能存在栈溢出风险。这时可以用迭代法替代例如用栈实现前序遍历def preorder_iterative(root): stack [root] while stack: node stack.pop() if node: print(node.val) stack.append(node.right) # 右子节点先入栈 stack.append(node.left) # 左子节点后入栈2. 判断相同树与子树匹配2.1 判断两棵树是否相同这个问题看似简单却是很多复杂问题的基础。核心思路是同步遍历两棵树比较每个节点的结构和值。递归解法的时间复杂度是O(n)空间复杂度取决于树的高度。def isSameTree(p, q): if not p and not q: # 都为空 return True if not p or not q: # 一个为空一个不为空 return False if p.val ! q.val: # 值不相等 return False return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)这个解法有几个关键点需要注意终止条件要处理所有可能的空节点情况先判断结构再判断值递归调用要同时比较左右子树2.2 子树匹配问题子树匹配可以复用相同树的判断逻辑。基本思路是对主树的每个节点都作为根节点判断是否与目标子树相同。最坏情况下时间复杂度是O(mn)其中m和n分别是两棵树的节点数。优化版的解法def isSubtree(root, subRoot): if not subRoot: return True if not root: return False if isSameTree(root, subRoot): return True return isSubtree(root.left, subRoot) or isSubtree(root.right, subRoot)实际工程中如果树很大可以考虑序列化后使用字符串匹配算法如KMP将时间复杂度优化到O(mn)。3. 二叉树深度相关问题3.1 计算最大深度最大深度是指从根节点到最远叶子节点的最长路径上的节点数。递归解法非常直观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迭代法可以使用层序遍历记录遍历的层数def maxDepth_iterative(root): if not root: return 0 queue [root] depth 0 while queue: depth 1 level_size len(queue) for _ in range(level_size): node queue.pop(0) if node.left: queue.append(node.left) if node.right: queue.append(node.right) return depth3.2 判断平衡二叉树平衡二叉树是指每个节点的左右子树高度差不超过1。直接按照定义实现的解法时间复杂度是O(n²)因为对每个节点都要计算子树高度def isBalanced(root): if not root: return True left_height maxDepth(root.left) right_height maxDepth(root.right) return abs(left_height - right_height) 1 and \ isBalanced(root.left) and \ isBalanced(root.right)更高效的O(n)解法是在计算高度的同时判断平衡性def isBalanced(root): def check(node): if not node: return 0 left check(node.left) right check(node.right) if left -1 or right -1 or abs(left - right) 1: return -1 return max(left, right) 1 return check(root) ! -14. 对称二叉树与进阶问题4.1 判断对称二叉树对称二叉树是指左右子树互为镜像。解决思路是比较左子树的左节点和右子树的右节点以及左子树的右节点和右子树的左节点。def isSymmetric(root): def compare(left, right): if not left and not right: return True if not left or not right: return False return left.val right.val and \ compare(left.left, right.right) and \ compare(left.right, right.left) return compare(root.left, root.right) if root else True迭代法可以使用队列实现def isSymmetric_iterative(root): if not root: return True queue [(root.left, root.right)] while queue: left, 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, right.right)) queue.append((left.right, right.left)) return True4.2 二叉树路径问题二叉树路径问题是面试中的高频考点。比如求从根节点到叶子节点的所有路径def binaryTreePaths(root): def dfs(node, path, res): if not node: return path.append(str(node.val)) if not node.left and not node.right: res.append(-.join(path)) dfs(node.left, path, res) dfs(node.right, path, res) path.pop() res [] dfs(root, [], res) return res路径问题通常需要结合回溯思想在递归调用前后维护当前路径状态。