1. 二叉树基础概念与核心特性二叉树是每个节点最多有两个子节点的树形数据结构这两个子节点分别称为左子节点和右子节点。在算法领域二叉树是最基础也是最重要的数据结构之一几乎所有的树形结构问题最终都会转化为二叉树问题来处理。1.1 二叉树的基本类型满二叉树如果一棵二叉树的每一层节点数都达到最大值即第k层有2^(k-1)个节点且所有叶子节点都在同一层这样的二叉树称为满二叉树。满二叉树的特点是节点总数与树的高度呈指数关系。完全二叉树除了最底层外其他各层的节点数都达到最大值且最底层的节点都集中在左侧连续位置。这种结构在堆排序和优先队列中应用广泛因为它可以高效地用数组表示而不需要指针。二叉搜索树(BST)一种有序的二叉树结构对于任意节点左子树所有节点的值小于当前节点值右子树所有节点的值大于当前节点值左右子树也必须是二叉搜索树BST的平均查找时间复杂度为O(log n)但在最坏情况下退化成链表会变为O(n)。平衡二叉搜索树(AVL树)在BST基础上增加了平衡条件要求任意节点的左右子树高度差不超过1。通过旋转操作保持平衡确保查找效率始终维持在O(log n)。实际工程中C的map/set和Java的TreeMap/TreeSet底层都是红黑树一种近似平衡的BST而非严格的AVL树因为红黑树在插入删除时需要的旋转操作更少。1.2 二叉树的存储方式链式存储struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };这是最直观的表示方法每个节点通过指针连接子节点。面试手写代码时务必注意指针初始化为nullptr。顺序存储数组表示 对于完全二叉树可以用数组紧凑存储。若父节点索引为i则左子节点索引2*i 1右子节点索引2*i 2这种表示节省指针空间适合堆结构。但非完全二叉树会浪费数组空间。2. 二叉树的遍历方法论2.1 深度优先遍历(DFS)递归三要素确定递归函数的参数和返回值确定终止条件确定单层递归逻辑前序遍历中-左-右def preorder(root): if not root: return print(root.val) # 中 preorder(root.left) # 左 preorder(root.right) # 右中序遍历左-中-右BST的中序遍历结果是有序数组这是BST的重要性质。后序遍历左-右-中常用于计算子树性质如二叉树的直径问题。记忆技巧遍历顺序指的是中节点的处理位置2.2 迭代法实现DFS递归的本质是栈因此所有递归写法都可以改为迭代法。以前序遍历为例vectorint preorderTraversal(TreeNode* root) { vectorint res; stackTreeNode* st; if (root) st.push(root); while (!st.empty()) { TreeNode* node st.top(); st.pop(); res.push_back(node-val); if (node-right) st.push(node-right); // 右先入栈 if (node-left) st.push(node-left); // 左后入栈 } return res; }2.3 广度优先遍历(BFS)使用队列实现层序遍历可以计算二叉树的最小深度、右视图等问题ListListInteger levelOrder(TreeNode root) { ListListInteger res new ArrayList(); QueueTreeNode queue new LinkedList(); if (root ! null) queue.offer(root); while (!queue.isEmpty()) { int size queue.size(); ListInteger level new ArrayList(); for (int i 0; i size; i) { TreeNode node queue.poll(); level.add(node.val); if (node.left ! null) queue.offer(node.left); if (node.right ! null) queue.offer(node.right); } res.add(level); } return res; }3. 二叉树经典问题解析3.1 二叉树的最大深度递归解法def maxDepth(root): if not root: return 0 return 1 max(maxDepth(root.left), maxDepth(root.right))迭代解法层序遍历int maxDepth(TreeNode* root) { queueTreeNode* q; if (root) q.push(root); int depth 0; while (!q.empty()) { int size q.size(); depth; while (size--) { TreeNode* node q.front(); q.pop(); if (node-left) q.push(node-left); if (node-right) q.push(node-right); } } return depth; }3.2 对称二叉树判断public boolean isSymmetric(TreeNode root) { return root null || check(root.left, root.right); } boolean check(TreeNode left, TreeNode right) { if (left null right null) return true; if (left null || right null) return false; return left.val right.val check(left.left, right.right) check(left.right, right.left); }3.3 路径总和问题def hasPathSum(root, target): if not root: return False if not root.left and not root.right: return root.val target return hasPathSum(root.left, target - root.val) or \ hasPathSum(root.right, target - root.val)4. 二叉搜索树专项4.1 BST验证bool isValidBST(TreeNode* root) { TreeNode* prev nullptr; stackTreeNode* st; while (root || !st.empty()) { while (root) { st.push(root); root root-left; } root st.top(); st.pop(); if (prev prev-val root-val) return false; prev root; root root-right; } return true; }4.2 BST插入操作public TreeNode insertIntoBST(TreeNode root, int val) { if (root null) return new TreeNode(val); if (val root.val) { root.left insertIntoBST(root.left, val); } else { root.right insertIntoBST(root.right, val); } return root; }5. 二叉树构造问题5.1 从前序与中序遍历序列构造二叉树def buildTree(preorder, inorder): if not preorder: return None root_val preorder[0] root TreeNode(root_val) idx inorder.index(root_val) root.left buildTree(preorder[1:1idx], inorder[:idx]) root.right buildTree(preorder[1idx:], inorder[idx1:]) return root5.2 从后序与中序遍历序列构造二叉树TreeNode* buildTree(vectorint inorder, vectorint postorder) { if (inorder.empty()) return nullptr; int root_val postorder.back(); TreeNode* root new TreeNode(root_val); auto it find(inorder.begin(), inorder.end(), root_val); int left_size distance(inorder.begin(), it); vectorint left_in(inorder.begin(), it); vectorint right_in(it 1, inorder.end()); vectorint left_post(postorder.begin(), postorder.begin() left_size); vectorint right_post(postorder.begin() left_size, postorder.end() - 1); root-left buildTree(left_in, left_post); root-right buildTree(right_in, right_post); return root; }6. 二叉树进阶技巧6.1 Morris遍历一种空间复杂度O(1)的遍历方法通过利用叶子节点的空指针实现public ListInteger inorderTraversal(TreeNode root) { ListInteger res new ArrayList(); TreeNode curr root; while (curr ! null) { if (curr.left null) { res.add(curr.val); curr curr.right; } else { TreeNode prev curr.left; while (prev.right ! null prev.right ! curr) { prev prev.right; } if (prev.right null) { prev.right curr; curr curr.left; } else { prev.right null; res.add(curr.val); curr curr.right; } } } return res; }6.2 序列化与反序列化def serialize(root): if not root: return null return f{root.val},{serialize(root.left)},{serialize(root.right)} def deserialize(data): def helper(nodes): val next(nodes) if val null: return None node TreeNode(int(val)) node.left helper(nodes) node.right helper(nodes) return node return helper(iter(data.split(,)))7. 常见错误与调试技巧空指针问题递归时忘记检查root是否为null遍历顺序混淆前中后序代码相似容易写混BST边界错误处理BST时等号条件处理不当递归栈溢出树深度过大时可能引发栈溢出修改原树结构某些问题需要先复制树结构再操作调试建议先画小规模树结构3-5个节点使用print或debugger跟踪递归过程对特殊case单独测试空树、单节点、斜树等8. 二叉树题目训练路线建议按照以下顺序刷题基础遍历前中后序层序简单属性判断对称、平衡等路径相关问题构造类问题BST专项进阶问题LCA、序列化等重点题目推荐二叉树的最大深度平衡二叉树二叉树中的最大路径和二叉树的最近公共祖先二叉树的序列化与反序列化