1. 二叉树基础概念与核心特性二叉树是每个节点最多有两个子节点的树结构这两个子节点分别称为左子节点和右子节点。这种数据结构在计算机科学中应用极为广泛从数据库索引到编译器设计都能看到它的身影。二叉树最基础的形态由根节点、左子树和右子树组成。空树是二叉树的特例而只有一个根节点的树是最简单的非空二叉树。在实际应用中我们经常会遇到以下几种特殊二叉树类型满二叉树每个节点都有0个或2个子节点且所有叶子节点都在同一层完全二叉树除最后一层外其他层节点数都达到最大值且最后一层节点都集中在左侧二叉搜索树(BST)左子树所有节点值小于根节点右子树所有节点值大于根节点平衡二叉树(AVL)任何节点的左右子树高度差不超过1提示理解二叉树的性质是解决相关问题的第一步。特别是二叉搜索树的特性左根右这将成为许多算法的基础。二叉树的高度深度是指从根节点到最远叶子节点的最长路径上的节点数。计算二叉树高度是常见的面试题通常采用递归方式实现def tree_height(root): if not root: return 0 return max(tree_height(root.left), tree_height(root.right)) 12. 二叉树的遍历方法与实现遍历二叉树是处理树结构的基础操作主要有四种经典遍历方式它们的核心区别在于访问根节点的时机不同。2.1 前序遍历Pre-order访问顺序根节点 → 左子树 → 右子树 应用场景复制树结构、序列化二叉树 递归实现def preorder(root): if root: print(root.val) preorder(root.left) preorder(root.right)2.2 中序遍历In-order访问顺序左子树 → 根节点 → 右子树 应用场景二叉搜索树得到有序序列 迭代实现使用栈def inorder(root): stack [] curr root while curr or stack: while curr: stack.append(curr) curr curr.left curr stack.pop() print(curr.val) curr curr.right2.3 后序遍历Post-order访问顺序左子树 → 右子树 → 根节点 应用场景删除树节点、表达式树求值 递归实现def postorder(root): if root: postorder(root.left) postorder(root.right) print(root.val)2.4 层序遍历Level-order按层次从上到下、每层从左到右访问节点 应用场景打印树结构、找最大宽度 队列实现from collections import deque def level_order(root): if not root: return queue deque([root]) while queue: node queue.popleft() print(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right)注意递归实现的遍历代码简洁但可能栈溢出对于深度很大的树应考虑迭代实现。层序遍历是唯一需要额外数据结构队列支持的遍历方式。3. 常见二叉树问题解析3.1 验证二叉搜索树判断二叉树是否为有效的二叉搜索树需要利用BST的性质中序遍历结果为升序序列。错误解法陷阱# 这种只检查当前节点与左右子节点的解法是错误的 def is_bst(root): if not root: return True if root.left and root.left.val root.val: return False if root.right and root.right.val root.val: return False return is_bst(root.left) and is_bst(root.right)正确解法中序遍历验证def is_bst(root): prev float(-inf) stack [] curr root while curr or stack: while curr: stack.append(curr) curr curr.left curr stack.pop() if curr.val prev: return False prev curr.val curr curr.right return True3.2 二叉树的最大深度与最小深度最大深度即树的高度而最小深度是指从根节点到最近叶子节点的最短路径上的节点数。最大深度递归def max_depth(root): if not root: return 0 return 1 max(max_depth(root.left), max_depth(root.right))最小深度BFS更高效from collections import deque def min_depth(root): if not root: return 0 queue deque([(root, 1)]) while queue: node, depth queue.popleft() if not node.left and not node.right: return depth if node.left: queue.append((node.left, depth 1)) if node.right: queue.append((node.right, depth 1))3.3 对称二叉树判断检查二叉树是否镜像对称可以通过比较左右子树是否互为镜像。递归解法def is_symmetric(root): 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) if root else True迭代解法使用队列from collections import deque def is_symmetric(root): if not root: return True queue deque([root.left, root.right]) while queue: left queue.popleft() right queue.popleft() if not left and not right: continue if not left or not right or left.val ! right.val: return False queue.append(left.left) queue.append(right.right) queue.append(left.right) queue.append(right.left) return True4. 高级二叉树问题与优化4.1 二叉树的序列化与反序列化将二叉树转换为字符串表示序列化以及从字符串重建二叉树反序列化是实际工程中的常见需求。前序遍历序列化实现def serialize(root): def helper(node): if not node: vals.append(#) return vals.append(str(node.val)) helper(node.left) helper(node.right) vals [] helper(root) return .join(vals) def deserialize(data): def helper(): val next(vals) if val #: return None node TreeNode(int(val)) node.left helper() node.right helper() return node vals iter(data.split()) return helper()4.2 最近公共祖先(LCA)问题找到二叉树中两个节点的最近公共祖先是面试中的高频题目。递归解法def lowest_common_ancestor(root, p, q): if not root or root p or root q: return root left lowest_common_ancestor(root.left, p, q) right lowest_common_ancestor(root.right, p, q) if left and right: return root return left if left else right对于BST的优化解法利用BST性质def lowest_common_ancestor(root, p, q): while root: if root.val p.val and root.val q.val: root root.left elif root.val p.val and root.val q.val: root root.right else: return root4.3 二叉树中的路径和问题检查二叉树中是否存在从根到叶子节点的路径使得路径上所有节点值之和等于给定值。递归解法def has_path_sum(root, target): if not root: return False if not root.left and not root.right and root.val target: return True return (has_path_sum(root.left, target - root.val) or has_path_sum(root.right, target - root.val))找出所有满足条件的路径def path_sum(root, target): def dfs(node, path, remaining): if not node: return path.append(node.val) if not node.left and not node.right and remaining node.val: res.append(list(path)) dfs(node.left, path, remaining - node.val) dfs(node.right, path, remaining - node.val) path.pop() res [] dfs(root, [], target) return res在实际编码面试中二叉树问题往往考察递归思维和对树结构的理解。我建议从基础遍历开始掌握逐步过渡到更复杂的问题。对于递归解法一定要明确基线条件递归终止条件和递归条件这是写出正确递归代码的关键。