一、基础二叉树结点定义struct TreeNode { int val; TreeNode *left; // 左孩子 TreeNode *right; // 右孩子 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };部分内容作用1TreeNode(int x)构造函数的声明参数x是要给结点赋的数值2:初始化列表的开始标志必须写在构造函数参数列表后面、函数体前面3val(x), left(nullptr), right(nullptr)初始化列表依次初始化 3 个成员变量4{}构造函数的函数体这里是空的因为所有初始化都在列表里完成了二、核心模板 1二叉树的 4 种遍历递归 迭代1. 前序遍历根→左→右// 递归版推荐蓝桥杯结点数≤1000不会栈溢出 void preorder(TreeNode* root, vectorint res) { if (!root) return; res.push_back(root-val); // 1. 访问根 preorder(root-left, res); // 2. 递归左子树 preorder(root-right, res); // 3. 递归右子树 } // 迭代版栈实现可选 void preorder_iter(TreeNode* root, vectorint res) { if (!root) return; stackTreeNode* stk; stk.push(root); while (!stk.empty()) { TreeNode* node stk.top(); stk.pop(); res.push_back(node-val); // 栈是后进先出先压右再压左保证左先出 if (node-right) stk.push(node-right); if (node-left) stk.push(node-left); } }2. 中序遍历左→根→右// 递归版 void inorder(TreeNode* root, vectorint res) { if (!root) return; inorder(root-left, res); // 1. 递归左子树 res.push_back(root-val); // 2. 访问根 inorder(root-right, res); // 3. 递归右子树 } // 迭代版栈实现可选 void inorder_iter(TreeNode* root, vectorint res) { if (!root) return; stackTreeNode* stk; TreeNode* cur root; while (cur || !stk.empty()) { while (cur) { // 一直往左走压栈 stk.push(cur); cur cur-left; } cur stk.top(); stk.pop(); res.push_back(cur-val); cur cur-right; // 转向右子树 } }3. 后序遍历左→右→根// 递归版 void postorder(TreeNode* root, vectorint res) { if (!root) return; postorder(root-left, res); // 1. 递归左子树 postorder(root-right, res); // 2. 递归右子树 res.push_back(root-val); // 3. 访问根 }4. 层序遍历BFS队列实现高频考点// 层序遍历按层输出返回一维数组蓝桥杯常用 void levelorder(TreeNode* root, vectorint res) { if (!root) return; queueTreeNode* q; q.push(root); while (!q.empty()) { TreeNode* node q.front(); q.pop(); res.push_back(node-val); if (node-left) q.push(node-left); // 左孩子入队 if (node-right) q.push(node-right); // 右孩子入队 } } // 进阶按层输出二维数组每层单独一行可选 vectorvectorint levelorder_by_level(TreeNode* root) { vectorvectorint res; if (!root) return res; queueTreeNode* q; q.push(root); while (!q.empty()) { int size q.size(); // 当前层的结点数 vectorint level; for (int i 0; i size; i) { TreeNode* node q.front(); q.pop(); level.push_back(node-val); if (node-left) q.push(node-left); if (node-right) q.push(node-right); } res.push_back(level); } return res; }三、核心模板 2前序 中序构造二叉树高频综合考点// 辅助哈希表快速查找中序序列中根结点的索引优化时间复杂度 unordered_mapint, int inorder_map; // 递归构造函数 // 参数preorder-前序数组inorder-中序数组pre_l/pre_r-当前前序区间in_l/in_r-当前中序区间 TreeNode* buildTree(vectorint preorder, vectorint inorder, int pre_l, int pre_r, int in_l, int in_r) { if (pre_l pre_r || in_l in_r) return nullptr; // 递归终止区间为空 int root_val preorder[pre_l]; // 前序首元素是根 TreeNode* root new TreeNode(root_val); int root_pos inorder_map[root_val]; // 中序中根的索引 int left_size root_pos - in_l; // 左子树的结点数 // 递归构造左子树前序区间[pre_l1, pre_lleft_size]中序区间[in_l, root_pos-1] root-left buildTree(preorder, inorder, pre_l1, pre_lleft_size, in_l, root_pos-1); // 递归构造右子树前序区间[pre_lleft_size1, pre_r]中序区间[root_pos1, in_r] root-right buildTree(preorder, inorder, pre_lleft_size1, pre_r, root_pos1, in_r); return root; } // 对外调用的简化接口 TreeNode* buildTree(vectorint preorder, vectorint inorder) { int n preorder.size(); inorder_map.clear(); for (int i 0; i n; i) { inorder_map[inorder[i]] i; // 建立中序值到索引的映射 } return buildTree(preorder, inorder, 0, n-1, 0, n-1); }四、核心模板 3二叉树的镜面反转结构修改// 递归版交换所有非叶结点的左右孩子 void mirrorTree(TreeNode* root) { if (!root) return; // 递归终止空结点 // 交换左右孩子 swap(root-left, root-right); // 递归处理左、右子树 mirrorTree(root-left); mirrorTree(root-right); }五、核心模板 4二叉树的属性计算1. 树的深度 / 高度int treeDepth(TreeNode* root) { if (!root) return 0; // 空树深度0 int left_depth treeDepth(root-left); int right_depth treeDepth(root-right); return max(left_depth, right_depth) 1; // 左右子树最大深度1 }2. 叶子结点个数int countLeaves(TreeNode* root) { if (!root) return 0; if (!root-left !root-right) return 1; // 叶结点左右都空 return countLeaves(root-left) countLeaves(root-right); }