我把二叉树的高频题都系统做了一遍并进行了整理层序遍历、最大深度、平衡二叉树、最小深度、根据前序中序重建二叉树里面包含我自己的错误代码、反思、正确解法、优化版本。持续更新中会更新九道题一、二叉树的层序遍历层序遍历是二叉树最基础的 BFS 模板也是很多题目的基础102. 二叉树的层序遍历思路使用队列从根节点开始一层一层向下遍历核心思想利用队列保存待访问的节点然后依次出队、将其孩子入队步骤根节点入队→队非空进行循环取出队头节点访问该节点左右孩子入队若有→直到队空通用代码C语言// 层次遍历 void LevelOrder(BiTree bt) { if (bt NULL) { return; } BiTNode* queue[100]; // 队头和队尾 int front 0; int rear 0; queue[rear] bt;// 根结点入队 while (front ! rear) { BiTNode* p queue[front]; // 输出队头元素的值 printf(%c , p-data); // 队头元素出队 front; // 将队头元素的左右孩子节点入队 if (p-lchild ! NULL) { queue[rear] p-lchild; } if (p-rchild ! NULL) { queue[rear] p-rchild; } } }leetcode代码这里的返回值是不定长的二维数组要额外注意将节点值存放到数组中的方法每一层都需要创建一个不定长的一维数组来保存当前层节点的值然后将一维数组放入二维数组先通过q.size()获取节点个数再用for循环遍历当前层的所有节点class Solution { public: vectorvectorint levelOrder(TreeNode* root) { if (root NULL) { return {}; } vectorvectorint res; queueTreeNode* q; // 根结点入队 q.push(root); while (!q.empty()) { // 当前层的节点数 int levelSize q.size(); // 创建动态数组 vectorint line; // 取出当前层的节点值 for (int i 0; i levelSize; i) { TreeNode* cur q.front(); // 队头元素 // 队头元素放入结果数组 line.push_back(cur-val); // 队头元素出队 q.pop(); // 队头元素的左右孩子节点入队 if (cur-left ! NULL) q.push(cur-left); if (cur-right ! NULL) q.push(cur-right); } res.push_back(line); } return res; } };二、二叉树的最大深度104. 二叉树的最大深度解法一递归 / 深度优先 DFS树的深度 左右子树的度的较大值 1所以可以使用递归的方法来实现求出左右子树的深度返回较大值1代码class Solution { public: int maxDepth(TreeNode* root) { // 树为空返回0 if (root NULL) { return 0; } // 求左右子树的度 int left maxDepth(root-left); int right maxDepth(root-right); // 树的深度左右子树的度的较大值 1 return max(left, right) 1; } };解法二广度优先与层次遍历树的方法类似获取当前层的节点数开始遍历当前层的节点树的层数树的最大深度class Solution { public: int maxDepth(TreeNode* root) { // 广度优先搜索 if (root NULL) { return 0; } int res 0;// 层数初始值为0 queueTreeNode* q; q.push(root); while (!q.empty()) { int count q.size(); // 当前层的节点数 // 遍历每一层的节点将节点的左右孩子放入队 while (count 0) { TreeNode* cur q.front(); q.pop(); if (cur-left ! NULL) { q.push(cur-left); } if (cur-right ! NULL) { q.push(cur-right); } count--; } res; // 每一层结束深度1层数就是最大深度 } return res; } };三、平衡二叉树110. 平衡二叉树复用函数 maxDepth 求树的高度判断左右子树是否平衡不平衡直接返回 false判断左右子树的深度差是否1深度从根来往下走高度到叶去往上数虽然是不一样的概念但是 左右子树高度差不超过1 和 深度差不超过1 是一样的所以直接利用上面的求深度函数就行class Solution { public: int maxDepth(TreeNode* root) { // 树为空返回0 if (root NULL) { return 0; } // 求左右子树的度 int left maxDepth(root-left); int right maxDepth(root-right); // 树的深度左右子树的度的较大值 1 return max(left, right) 1; } bool isBalanced(TreeNode* root) { // 树为空返回true if (root NULL) { return true; } // 判断左右子树是否平衡 bool leftTree isBalanced(root-left); if (!leftTree) return false; bool rightTree isBalanced(root-right); if (!rightTree) return false; // 判断左右子树的深度差是否1 int leftDepth maxDepth(root-left); int rightDepth maxDepth(root-right); return abs(leftDepth - rightDepth) 1; } };官方题解思路补充解法一自顶向下class Solution { public boolean isBalanced(TreeNode root) { if (root null) { return true; } else { return Math.abs(height(root.left) - height(root.right)) 1 isBalanced(root.left) isBalanced(root.right); } } public int height(TreeNode root) { if (root null) { return 0; } else { return Math.max(height(root.left), height(root.right)) 1; } } }解法二自下往上class Solution { public boolean isBalanced(TreeNode root) { return height(root) 0; } public int height(TreeNode root) { if (root null) { return 0; } int leftHeight height(root.left); int rightHeight height(root.right); if (leftHeight -1 || rightHeight -1 || Math.abs(leftHeight - rightHeight) 1) { return -1; } else { return Math.max(leftHeight, rightHeight) 1; } } }四、二叉树的最小深度111. 二叉树的最小深度解法一递归 / 深度优先错误代码class Solution { public: int minDepth(TreeNode* root) { // 空树返回0 if (root NULL) { return 0; } // 求左右子树的最小深度 int l minDepth(root-left); int r minDepth(root-right); // 树的最小深度左右子树的最小深度的较小值1根节点 if (l r) return l 1; else return r 1; } };错误原因最小深度不是左右最小 1而是必须到叶子如果一棵树左子树为空、右子树有深度那么直接返回min(0, r)1但逻辑上应该走右子树深度而不是算 0。正确代码必须分情况左空 → 走右右空 → 走左都不空 → 取最小 1class Solution { public: int minDepth(TreeNode* root) { // 空树返回0 if (root NULL) { return 0; } // 求左右子树的最小深度 int l minDepth(root-left); int r minDepth(root-right); if (l 0) // 左子树为空 return r 1; else if (r 0) // 右子树为空 return l 1; else if (l r) return l 1; else return r 1; } };解法二广度优先搜索 BFS与“求二叉树的最大深度”的解法二类似但是此处遇到一个节点无左右孩子节点就直接返回已记录的层数class Solution { public: int minDepth(TreeNode* root) { // 广度优先搜索 if (root NULL) { return 0; } int res 1; queueTreeNode* q; q.push(root); while (!q.empty()) { int count q.size(); // 当前层的节点数 while (count 0) { TreeNode* cur q.front(); // 队头元素 q.pop(); // 出队 // 若当前节点没有左右孩子→此处即为最近的叶子节点 if (cur-left NULL cur-right NULL) { return res; } if (cur-left ! NULL) { q.push(cur-left); } if (cur-right ! NULL) { q.push(cur-right); } count--; } res; } return res; } };五、推理二叉树LCR 124. 推理二叉树解法递归核心思路前序的第一个值是根节点在中序中找到根节点 → 左边是左子树右边是右子树继续递归构造左右子树错误代码问题直接 erase(begin()) 会导致后续递归使用的 preorder 被破坏多次操作非常不安全class Solution { public: TreeNode* deduceTree(vectorint preorder, vectorint inorder) { int val preorder[0];// 根节点的值 TreeNode* root new TreeNode(val); // 创建根节点 // 当前只剩root节点直接返回 if (inorder.size() 1) { return root; } // 用两个数组保存左右子树的中序遍历数组 vectorint leftTree; vectorint rightTree; bool flag false;// 标志是否遍历到值val for (int i 0; i inorder.size(); i) { if (inorder[i] val) {// 遍历到val将flag改为true flag true; } else if (flag) { // flag为true后的节点值均为右子树的节点的值 rightTree.push_back(inorder[i]); } else { // flag为true前的节点值均为左子树的节点的值 leftTree.push_back(inorder[i]); } } if (!preorder.empty()) { // 更新先序遍历数组 preorder.erase(preorder.begin()); // 删除第一个元素 } root-left deduceTree(preorder, leftTree); // 构造左子树 if (!preorder.empty()) { preorder.erase(preorder.begin()); // 删除第一个元素 } root-right deduceTree(preorder, rightTree); // 构造右子树 return root; } };修正代码仍然不安全但逻辑正确class Solution { public: TreeNode* deduceTree(vectorint preorder, vectorint inorder) { if (inorder.size() 0 || preorder.size() 0) { return NULL; } int val preorder[0]; TreeNode* root new TreeNode(val); vectorint leftTree; vectorint rightTree; bool flag false; for (int i 0; i inorder.size(); i) { if (inorder[i] val) { flag true; } else if (flag) { rightTree.push_back(inorder[i]); } else { leftTree.push_back(inorder[i]); } } preorder.erase(preorder.begin()); // 只删除第一个元素 root-left deduceTree(preorder, leftTree); root-right deduceTree(preorder, rightTree); return root; } };更优代码使用 find 迭代器构造 vectorfind 查找根节点在中序中的位置用迭代器区间直接构造 left /right避免循环class Solution { public: TreeNode* deduceTree(vectorint preorder, vectorint inorder) { if (inorder.empty() || preorder.empty()) return nullptr; int val preorder[0]; TreeNode* root new TreeNode(val); // 在中序遍历数组中寻找值val auto it find(inorder.begin(), inorder.end(), val); // 创建左右子树的中序遍历数组 vectorint inleft(inorder.begin(), it); vectorint inright(it 1, inorder.end()); preorder.erase(preorder.begin());// 删除已确定的节点 // 构造左右子树 root-left deduceTree(preorder, inleft); root-right deduceTree(preorder, inright); return root; } };C语言代码C 语言不能用 vector需要用指针偏移和递归区间。/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize) { // 无先序数组/中序数组→返回NULL if (preorderSize 0 || inorderSize 0) { return NULL; } // 1.根据先序数组得到根节点 // 2.遍历中序数组找到val的下标 // 3.传递正确的参数构造左右子树 int val preorder[0]; // 根节点的值 struct TreeNode* root (struct TreeNode*)malloc(sizeof(struct TreeNode)); // 创建一个根节点 root-val val; // 值为val // 初始化左右子树 root-left NULL; root-right NULL; // 找到中序数组中val的下标 int mid 0; while (inorder[mid] ! val) mid; // 说明当mid为val的下标时 // 中序数组中左子树节点树mid // 右子树节点树inorderSize-mid-1 // 则左子树的先序数组的数字个数mid // 右子树的先序数组的数字个数preorderSize-mid-1 // 构造左右子树 root-left buildTree(preorder 1, mid, inorder, mid); root-right buildTree(preorder 1 mid, preorderSize - mid - 1, inorder mid 1, inorderSize - mid - 1); return root; }注意点申请节点需要使用malloc申请不然无法初始化递归区间不要写错preorder1 是关键左子树节点数 mid中序中 val 左边个数右子树节点数 preorderSize - mid - 1六、中序遍历94. 二叉树的中序遍历这道题的返回值是vector递归法必须要通过辅助函数来实现题目给的主函数的参数是固定死的不能修改递归必须使用同一个vector保存结果如果不另写一个辅助函数每次递归都会创建一个新的vectorint迭代法可以不使用辅助函数但使用后代码更清晰更安全解法一递归法class Solution { public: void inorder(TreeNode* root, vectorint res) { if (root NULL) { return; } else { // 先遍历左子树 inorder(root-left, res); // 再打印当前节点 res.push_back(root-val); // 再遍历右子树 inorder(root-right, res); } } vectorint inorderTraversal(TreeNode* root) { vectorint res; inorder(root,res); return res; } };解法二迭代法另写辅助函数class Solution { public: void inorder(TreeNode* root, vectorint res) { // 迭代非递归写法 if (root NULL) { return; } stackTreeNode* st; TreeNode* cur root; // 遍历左子树 while (cur ! NULL || !st.empty()) { if(cur ! NULL){ st.push(cur);// 根节点入栈 curcur-left;// 遍历左子树 } else{ curst.top(); st.pop(); res.push_back(cur-val); curcur-right; } } } vectorint inorderTraversal(TreeNode* root) { vectorint res; inorder(root, res); return res; } };无辅助函数class Solution { public: vectorint inorderTraversal(TreeNode* root) { // 迭代非递归写法 vectorint res; stackTreeNode* st; while (root ! NULL || !st.empty()) { // 将左子树的根节点压入栈 while (root ! NULL) { st.push(root); // 根节点入栈 root root-left; } root st.top(); st.pop(); res.push_back(root-val); root root-right;// 遍历右子树 } return res; } };七、相同的树100. 相同的树递归核心步骤先处理特殊情况两棵树均为空/其中一个树为空比较当前节点的val比较左子树若左子树不等→直接返回false无需再比较右子树比较右子树返回右子树比较结果class Solution { public: bool isSameTree(TreeNode* p, TreeNode* q) { if (p NULL q NULL) { // 两棵树都是空树 return true; } else if (p NULL) { // p是空树 return false; } else if (q NULL) { // q是空树 return false; } // 同时遍历两棵树的每个节点一一比较 // 使用先序/中序/后序遍历都可以 TreeNode* cur1 p; TreeNode* cur2 q; bool res1, res2; if (cur1-val ! cur2-val) { return false; } // 比较左子树 res1 isSameTree(cur1-left, cur2-left); if (!res1) { return false; } // 比较右子树 res2 isSameTree(cur1-right, cur2-right); return res2; } };广度优先搜索class Solution { public: bool isSameTree(TreeNode* p, TreeNode* q) { if (p NULL q NULL) { return true; } else if (p NULL || q NULL) { return false; } // 使用两个队列遍历两棵树 queueTreeNode* q1; queueTreeNode* q2; // 根节点入队 q1.push(p); q2.push(q); while (!q1.empty() !q2.empty()) { // 队头元素 TreeNode* cur1 q1.front(); TreeNode* cur2 q2.front(); if (cur1-val ! cur2-val) { return false; } // 队头元素出队 q1.pop(); q2.pop(); // 左孩子入队 if (cur1-left ! NULL cur2-left ! NULL) { q1.push(cur1-left); q2.push(cur2-left); } else if (cur1-left ! NULL || cur2-left ! NULL) { return false; } // 右孩子入队 if (cur1-right ! NULL cur2-right ! NULL) { q1.push(cur1-right); q2.push(cur2-right); } else if (cur1-right ! NULL || cur2-right ! NULL) { return false; } } return true; } };八、对称二叉树101. 对称二叉树使用两个队列遍历保存根节点的左右子树class Solution { public: bool isSymmetric(TreeNode* root) { // 没有左右孩子 if(root-left NULL root-right NULL){ return true; }else if(root-left NULL || root-right NULL){ return false; // 只有左孩子或只有右孩子 } queueTreeNode* q1; // 存储左子树顶点 queueTreeNode* q2; // 存储右子树顶点 // 将根节点的左右孩子入队 q1.push(root-left); q2.push(root-right); while (!q1.empty() !q2.empty()) { // 比较两队队头 TreeNode* cur1 q1.front(); TreeNode* cur2 q2.front(); if (cur1-val ! cur2-val) { return false; } // 队头元素出队 q1.pop(); q2.pop(); // 左右孩子入队一个顺序为左右另一个顺序为右左 if (cur1-left ! NULL cur2-right ! NULL) { q1.push(cur1-left); q2.push(cur2-right); } // 其中一个为空则不对称 else if (cur1-left NULL || cur2-right NULL) { return false; } if (cur1-right ! NULL cur2-left ! NULL) { q1.push(cur1-right); q2.push(cur2-left); } // 其中一个为空则不对称 else if (cur1-right NULL || cur2-left NULL) { return false; } } // 两队同时为空则对称反之不对称 return q1.empty() q2.empty(); } };错误cur1-left NULL || cur2-right NULL 当两个均为NULL也为真但是会返回false所以逻辑存在错误修正// 左孩子 - 右孩子 对称判断 if (cur1-left ! NULL cur2-right ! NULL) { q1.push(cur1-left); q2.push(cur2-right); } else if (cur1-left NULL cur2-right NULL) { // 两个均为空不做任何处理 } else{ // 一个空一个非空 → 不对称 return false; } // 右孩子 - 左孩子 对称判断 if (cur1-right ! NULL cur2-left ! NULL) { q1.push(cur1-right); q2.push(cur2-left); } else if (cur1-right NULL cur2-left NULL) { // 两个均为空不做任何处理 } else{ // 一个空一个非空 → 不对称 return false; }更优写法// 左孩子 - 右孩子 对称判断 if (cur1-left ! NULL cur2-right ! NULL) { q1.push(cur1-left); q2.push(cur2-right); } else if (cur1-left NULL ^ cur2-right NULL) { // 一个空一个非空 → 不对称 return false; } // 右孩子 - 左孩子 对称判断 if (cur1-right ! NULL cur2-left ! NULL) { q1.push(cur1-right); q2.push(cur2-left); } else if (cur1-right NULL ^ cur2-left NULL) { // 一个空一个非空 → 不对称 return false; }官方题解解法一递归class Solution { public: bool check(TreeNode* p,TreeNode* q){ if(!p !q) return true;// 两者均为空 if(!p || !q) return false;// 其中一个为空 // 比较两者的当前节点值 // 比较两者的左右子树是否相等 return p-val q-val check(p-left, q-right) check(p-right, q-left); } bool isSymmetric(TreeNode* root) { return check(root-left, root-right); } };解法二迭代public: bool check(TreeNode* u, TreeNode* v) { queueTreeNode* q; // 使用一个队列同时保存左右子树 q.push(u); q.push(v); // 将左右子树的根节点入队 while (!q.empty()) { u q.front(); q.pop(); v q.front(); q.pop(); // 比较 if (!u !v) continue; // 若均为空则对称 // 若其中一个为空或值不相等则不对称 if ((!u || !v) || (u-val ! v-val)) return false; // u的左、v的右入队 q.push(u-left); q.push(v-right); // u的右、v的左入队 q.push(u-right); q.push(v-left); } return true; } bool isSymmetric(TreeNode* root) { return check(root, root); } };九、最大二叉树654. 最大二叉树学习总结二叉树核心的几类题整理层序遍历BFS 模板最大深度DFS、BFS 双解法最小深度陷阱题、必须区分空左右子树平衡二叉树递归判断深度差重建二叉树前序 中序 → 递归重建我真正理解了二叉树的题核心是递归结构 遍历顺序层序遍历是 BFS 的基础深度相关题目离不开 maxDepth重建树必须抓住 “前序找根中序分左右” 的套路
二叉树高频题全整理（层序遍历 / 最大深度 / 平衡树 / 最小深度 / 重建二叉树）
我把二叉树的高频题都系统做了一遍并进行了整理层序遍历、最大深度、平衡二叉树、最小深度、根据前序中序重建二叉树里面包含我自己的错误代码、反思、正确解法、优化版本。持续更新中会更新九道题一、二叉树的层序遍历层序遍历是二叉树最基础的 BFS 模板也是很多题目的基础102. 二叉树的层序遍历思路使用队列从根节点开始一层一层向下遍历核心思想利用队列保存待访问的节点然后依次出队、将其孩子入队步骤根节点入队→队非空进行循环取出队头节点访问该节点左右孩子入队若有→直到队空通用代码C语言// 层次遍历 void LevelOrder(BiTree bt) { if (bt NULL) { return; } BiTNode* queue[100]; // 队头和队尾 int front 0; int rear 0; queue[rear] bt;// 根结点入队 while (front ! rear) { BiTNode* p queue[front]; // 输出队头元素的值 printf(%c , p-data); // 队头元素出队 front; // 将队头元素的左右孩子节点入队 if (p-lchild ! NULL) { queue[rear] p-lchild; } if (p-rchild ! NULL) { queue[rear] p-rchild; } } }leetcode代码这里的返回值是不定长的二维数组要额外注意将节点值存放到数组中的方法每一层都需要创建一个不定长的一维数组来保存当前层节点的值然后将一维数组放入二维数组先通过q.size()获取节点个数再用for循环遍历当前层的所有节点class Solution { public: vectorvectorint levelOrder(TreeNode* root) { if (root NULL) { return {}; } vectorvectorint res; queueTreeNode* q; // 根结点入队 q.push(root); while (!q.empty()) { // 当前层的节点数 int levelSize q.size(); // 创建动态数组 vectorint line; // 取出当前层的节点值 for (int i 0; i levelSize; i) { TreeNode* cur q.front(); // 队头元素 // 队头元素放入结果数组 line.push_back(cur-val); // 队头元素出队 q.pop(); // 队头元素的左右孩子节点入队 if (cur-left ! NULL) q.push(cur-left); if (cur-right ! NULL) q.push(cur-right); } res.push_back(line); } return res; } };二、二叉树的最大深度104. 二叉树的最大深度解法一递归 / 深度优先 DFS树的深度 左右子树的度的较大值 1所以可以使用递归的方法来实现求出左右子树的深度返回较大值1代码class Solution { public: int maxDepth(TreeNode* root) { // 树为空返回0 if (root NULL) { return 0; } // 求左右子树的度 int left maxDepth(root-left); int right maxDepth(root-right); // 树的深度左右子树的度的较大值 1 return max(left, right) 1; } };解法二广度优先与层次遍历树的方法类似获取当前层的节点数开始遍历当前层的节点树的层数树的最大深度class Solution { public: int maxDepth(TreeNode* root) { // 广度优先搜索 if (root NULL) { return 0; } int res 0;// 层数初始值为0 queueTreeNode* q; q.push(root); while (!q.empty()) { int count q.size(); // 当前层的节点数 // 遍历每一层的节点将节点的左右孩子放入队 while (count 0) { TreeNode* cur q.front(); q.pop(); if (cur-left ! NULL) { q.push(cur-left); } if (cur-right ! NULL) { q.push(cur-right); } count--; } res; // 每一层结束深度1层数就是最大深度 } return res; } };三、平衡二叉树110. 平衡二叉树复用函数 maxDepth 求树的高度判断左右子树是否平衡不平衡直接返回 false判断左右子树的深度差是否1深度从根来往下走高度到叶去往上数虽然是不一样的概念但是 左右子树高度差不超过1 和 深度差不超过1 是一样的所以直接利用上面的求深度函数就行class Solution { public: int maxDepth(TreeNode* root) { // 树为空返回0 if (root NULL) { return 0; } // 求左右子树的度 int left maxDepth(root-left); int right maxDepth(root-right); // 树的深度左右子树的度的较大值 1 return max(left, right) 1; } bool isBalanced(TreeNode* root) { // 树为空返回true if (root NULL) { return true; } // 判断左右子树是否平衡 bool leftTree isBalanced(root-left); if (!leftTree) return false; bool rightTree isBalanced(root-right); if (!rightTree) return false; // 判断左右子树的深度差是否1 int leftDepth maxDepth(root-left); int rightDepth maxDepth(root-right); return abs(leftDepth - rightDepth) 1; } };官方题解思路补充解法一自顶向下class Solution { public boolean isBalanced(TreeNode root) { if (root null) { return true; } else { return Math.abs(height(root.left) - height(root.right)) 1 isBalanced(root.left) isBalanced(root.right); } } public int height(TreeNode root) { if (root null) { return 0; } else { return Math.max(height(root.left), height(root.right)) 1; } } }解法二自下往上class Solution { public boolean isBalanced(TreeNode root) { return height(root) 0; } public int height(TreeNode root) { if (root null) { return 0; } int leftHeight height(root.left); int rightHeight height(root.right); if (leftHeight -1 || rightHeight -1 || Math.abs(leftHeight - rightHeight) 1) { return -1; } else { return Math.max(leftHeight, rightHeight) 1; } } }四、二叉树的最小深度111. 二叉树的最小深度解法一递归 / 深度优先错误代码class Solution { public: int minDepth(TreeNode* root) { // 空树返回0 if (root NULL) { return 0; } // 求左右子树的最小深度 int l minDepth(root-left); int r minDepth(root-right); // 树的最小深度左右子树的最小深度的较小值1根节点 if (l r) return l 1; else return r 1; } };错误原因最小深度不是左右最小 1而是必须到叶子如果一棵树左子树为空、右子树有深度那么直接返回min(0, r)1但逻辑上应该走右子树深度而不是算 0。正确代码必须分情况左空 → 走右右空 → 走左都不空 → 取最小 1class Solution { public: int minDepth(TreeNode* root) { // 空树返回0 if (root NULL) { return 0; } // 求左右子树的最小深度 int l minDepth(root-left); int r minDepth(root-right); if (l 0) // 左子树为空 return r 1; else if (r 0) // 右子树为空 return l 1; else if (l r) return l 1; else return r 1; } };解法二广度优先搜索 BFS与“求二叉树的最大深度”的解法二类似但是此处遇到一个节点无左右孩子节点就直接返回已记录的层数class Solution { public: int minDepth(TreeNode* root) { // 广度优先搜索 if (root NULL) { return 0; } int res 1; queueTreeNode* q; q.push(root); while (!q.empty()) { int count q.size(); // 当前层的节点数 while (count 0) { TreeNode* cur q.front(); // 队头元素 q.pop(); // 出队 // 若当前节点没有左右孩子→此处即为最近的叶子节点 if (cur-left NULL cur-right NULL) { return res; } if (cur-left ! NULL) { q.push(cur-left); } if (cur-right ! NULL) { q.push(cur-right); } count--; } res; } return res; } };五、推理二叉树LCR 124. 推理二叉树解法递归核心思路前序的第一个值是根节点在中序中找到根节点 → 左边是左子树右边是右子树继续递归构造左右子树错误代码问题直接 erase(begin()) 会导致后续递归使用的 preorder 被破坏多次操作非常不安全class Solution { public: TreeNode* deduceTree(vectorint preorder, vectorint inorder) { int val preorder[0];// 根节点的值 TreeNode* root new TreeNode(val); // 创建根节点 // 当前只剩root节点直接返回 if (inorder.size() 1) { return root; } // 用两个数组保存左右子树的中序遍历数组 vectorint leftTree; vectorint rightTree; bool flag false;// 标志是否遍历到值val for (int i 0; i inorder.size(); i) { if (inorder[i] val) {// 遍历到val将flag改为true flag true; } else if (flag) { // flag为true后的节点值均为右子树的节点的值 rightTree.push_back(inorder[i]); } else { // flag为true前的节点值均为左子树的节点的值 leftTree.push_back(inorder[i]); } } if (!preorder.empty()) { // 更新先序遍历数组 preorder.erase(preorder.begin()); // 删除第一个元素 } root-left deduceTree(preorder, leftTree); // 构造左子树 if (!preorder.empty()) { preorder.erase(preorder.begin()); // 删除第一个元素 } root-right deduceTree(preorder, rightTree); // 构造右子树 return root; } };修正代码仍然不安全但逻辑正确class Solution { public: TreeNode* deduceTree(vectorint preorder, vectorint inorder) { if (inorder.size() 0 || preorder.size() 0) { return NULL; } int val preorder[0]; TreeNode* root new TreeNode(val); vectorint leftTree; vectorint rightTree; bool flag false; for (int i 0; i inorder.size(); i) { if (inorder[i] val) { flag true; } else if (flag) { rightTree.push_back(inorder[i]); } else { leftTree.push_back(inorder[i]); } } preorder.erase(preorder.begin()); // 只删除第一个元素 root-left deduceTree(preorder, leftTree); root-right deduceTree(preorder, rightTree); return root; } };更优代码使用 find 迭代器构造 vectorfind 查找根节点在中序中的位置用迭代器区间直接构造 left /right避免循环class Solution { public: TreeNode* deduceTree(vectorint preorder, vectorint inorder) { if (inorder.empty() || preorder.empty()) return nullptr; int val preorder[0]; TreeNode* root new TreeNode(val); // 在中序遍历数组中寻找值val auto it find(inorder.begin(), inorder.end(), val); // 创建左右子树的中序遍历数组 vectorint inleft(inorder.begin(), it); vectorint inright(it 1, inorder.end()); preorder.erase(preorder.begin());// 删除已确定的节点 // 构造左右子树 root-left deduceTree(preorder, inleft); root-right deduceTree(preorder, inright); return root; } };C语言代码C 语言不能用 vector需要用指针偏移和递归区间。/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize) { // 无先序数组/中序数组→返回NULL if (preorderSize 0 || inorderSize 0) { return NULL; } // 1.根据先序数组得到根节点 // 2.遍历中序数组找到val的下标 // 3.传递正确的参数构造左右子树 int val preorder[0]; // 根节点的值 struct TreeNode* root (struct TreeNode*)malloc(sizeof(struct TreeNode)); // 创建一个根节点 root-val val; // 值为val // 初始化左右子树 root-left NULL; root-right NULL; // 找到中序数组中val的下标 int mid 0; while (inorder[mid] ! val) mid; // 说明当mid为val的下标时 // 中序数组中左子树节点树mid // 右子树节点树inorderSize-mid-1 // 则左子树的先序数组的数字个数mid // 右子树的先序数组的数字个数preorderSize-mid-1 // 构造左右子树 root-left buildTree(preorder 1, mid, inorder, mid); root-right buildTree(preorder 1 mid, preorderSize - mid - 1, inorder mid 1, inorderSize - mid - 1); return root; }注意点申请节点需要使用malloc申请不然无法初始化递归区间不要写错preorder1 是关键左子树节点数 mid中序中 val 左边个数右子树节点数 preorderSize - mid - 1六、中序遍历94. 二叉树的中序遍历这道题的返回值是vector递归法必须要通过辅助函数来实现题目给的主函数的参数是固定死的不能修改递归必须使用同一个vector保存结果如果不另写一个辅助函数每次递归都会创建一个新的vectorint迭代法可以不使用辅助函数但使用后代码更清晰更安全解法一递归法class Solution { public: void inorder(TreeNode* root, vectorint res) { if (root NULL) { return; } else { // 先遍历左子树 inorder(root-left, res); // 再打印当前节点 res.push_back(root-val); // 再遍历右子树 inorder(root-right, res); } } vectorint inorderTraversal(TreeNode* root) { vectorint res; inorder(root,res); return res; } };解法二迭代法另写辅助函数class Solution { public: void inorder(TreeNode* root, vectorint res) { // 迭代非递归写法 if (root NULL) { return; } stackTreeNode* st; TreeNode* cur root; // 遍历左子树 while (cur ! NULL || !st.empty()) { if(cur ! NULL){ st.push(cur);// 根节点入栈 curcur-left;// 遍历左子树 } else{ curst.top(); st.pop(); res.push_back(cur-val); curcur-right; } } } vectorint inorderTraversal(TreeNode* root) { vectorint res; inorder(root, res); return res; } };无辅助函数class Solution { public: vectorint inorderTraversal(TreeNode* root) { // 迭代非递归写法 vectorint res; stackTreeNode* st; while (root ! NULL || !st.empty()) { // 将左子树的根节点压入栈 while (root ! NULL) { st.push(root); // 根节点入栈 root root-left; } root st.top(); st.pop(); res.push_back(root-val); root root-right;// 遍历右子树 } return res; } };七、相同的树100. 相同的树递归核心步骤先处理特殊情况两棵树均为空/其中一个树为空比较当前节点的val比较左子树若左子树不等→直接返回false无需再比较右子树比较右子树返回右子树比较结果class Solution { public: bool isSameTree(TreeNode* p, TreeNode* q) { if (p NULL q NULL) { // 两棵树都是空树 return true; } else if (p NULL) { // p是空树 return false; } else if (q NULL) { // q是空树 return false; } // 同时遍历两棵树的每个节点一一比较 // 使用先序/中序/后序遍历都可以 TreeNode* cur1 p; TreeNode* cur2 q; bool res1, res2; if (cur1-val ! cur2-val) { return false; } // 比较左子树 res1 isSameTree(cur1-left, cur2-left); if (!res1) { return false; } // 比较右子树 res2 isSameTree(cur1-right, cur2-right); return res2; } };广度优先搜索class Solution { public: bool isSameTree(TreeNode* p, TreeNode* q) { if (p NULL q NULL) { return true; } else if (p NULL || q NULL) { return false; } // 使用两个队列遍历两棵树 queueTreeNode* q1; queueTreeNode* q2; // 根节点入队 q1.push(p); q2.push(q); while (!q1.empty() !q2.empty()) { // 队头元素 TreeNode* cur1 q1.front(); TreeNode* cur2 q2.front(); if (cur1-val ! cur2-val) { return false; } // 队头元素出队 q1.pop(); q2.pop(); // 左孩子入队 if (cur1-left ! NULL cur2-left ! NULL) { q1.push(cur1-left); q2.push(cur2-left); } else if (cur1-left ! NULL || cur2-left ! NULL) { return false; } // 右孩子入队 if (cur1-right ! NULL cur2-right ! NULL) { q1.push(cur1-right); q2.push(cur2-right); } else if (cur1-right ! NULL || cur2-right ! NULL) { return false; } } return true; } };八、对称二叉树101. 对称二叉树使用两个队列遍历保存根节点的左右子树class Solution { public: bool isSymmetric(TreeNode* root) { // 没有左右孩子 if(root-left NULL root-right NULL){ return true; }else if(root-left NULL || root-right NULL){ return false; // 只有左孩子或只有右孩子 } queueTreeNode* q1; // 存储左子树顶点 queueTreeNode* q2; // 存储右子树顶点 // 将根节点的左右孩子入队 q1.push(root-left); q2.push(root-right); while (!q1.empty() !q2.empty()) { // 比较两队队头 TreeNode* cur1 q1.front(); TreeNode* cur2 q2.front(); if (cur1-val ! cur2-val) { return false; } // 队头元素出队 q1.pop(); q2.pop(); // 左右孩子入队一个顺序为左右另一个顺序为右左 if (cur1-left ! NULL cur2-right ! NULL) { q1.push(cur1-left); q2.push(cur2-right); } // 其中一个为空则不对称 else if (cur1-left NULL || cur2-right NULL) { return false; } if (cur1-right ! NULL cur2-left ! NULL) { q1.push(cur1-right); q2.push(cur2-left); } // 其中一个为空则不对称 else if (cur1-right NULL || cur2-left NULL) { return false; } } // 两队同时为空则对称反之不对称 return q1.empty() q2.empty(); } };错误cur1-left NULL || cur2-right NULL 当两个均为NULL也为真但是会返回false所以逻辑存在错误修正// 左孩子 - 右孩子 对称判断 if (cur1-left ! NULL cur2-right ! NULL) { q1.push(cur1-left); q2.push(cur2-right); } else if (cur1-left NULL cur2-right NULL) { // 两个均为空不做任何处理 } else{ // 一个空一个非空 → 不对称 return false; } // 右孩子 - 左孩子 对称判断 if (cur1-right ! NULL cur2-left ! NULL) { q1.push(cur1-right); q2.push(cur2-left); } else if (cur1-right NULL cur2-left NULL) { // 两个均为空不做任何处理 } else{ // 一个空一个非空 → 不对称 return false; }更优写法// 左孩子 - 右孩子 对称判断 if (cur1-left ! NULL cur2-right ! NULL) { q1.push(cur1-left); q2.push(cur2-right); } else if (cur1-left NULL ^ cur2-right NULL) { // 一个空一个非空 → 不对称 return false; } // 右孩子 - 左孩子 对称判断 if (cur1-right ! NULL cur2-left ! NULL) { q1.push(cur1-right); q2.push(cur2-left); } else if (cur1-right NULL ^ cur2-left NULL) { // 一个空一个非空 → 不对称 return false; }官方题解解法一递归class Solution { public: bool check(TreeNode* p,TreeNode* q){ if(!p !q) return true;// 两者均为空 if(!p || !q) return false;// 其中一个为空 // 比较两者的当前节点值 // 比较两者的左右子树是否相等 return p-val q-val check(p-left, q-right) check(p-right, q-left); } bool isSymmetric(TreeNode* root) { return check(root-left, root-right); } };解法二迭代public: bool check(TreeNode* u, TreeNode* v) { queueTreeNode* q; // 使用一个队列同时保存左右子树 q.push(u); q.push(v); // 将左右子树的根节点入队 while (!q.empty()) { u q.front(); q.pop(); v q.front(); q.pop(); // 比较 if (!u !v) continue; // 若均为空则对称 // 若其中一个为空或值不相等则不对称 if ((!u || !v) || (u-val ! v-val)) return false; // u的左、v的右入队 q.push(u-left); q.push(v-right); // u的右、v的左入队 q.push(u-right); q.push(v-left); } return true; } bool isSymmetric(TreeNode* root) { return check(root, root); } };九、最大二叉树654. 最大二叉树学习总结二叉树核心的几类题整理层序遍历BFS 模板最大深度DFS、BFS 双解法最小深度陷阱题、必须区分空左右子树平衡二叉树递归判断深度差重建二叉树前序 中序 → 递归重建我真正理解了二叉树的题核心是递归结构 遍历顺序层序遍历是 BFS 的基础深度相关题目离不开 maxDepth重建树必须抓住 “前序找根中序分左右” 的套路
