1. 为什么OJ上的二叉树题总是“看着简单一写就废”1.1 二叉树是新手第一次正经接触“递归”这种反直觉的东西做OJ题的时候数组、链表、栈、队列这些线性结构你靠一层for循环、一个while循环基本就能搞定思路是顺着来的从头走到尾或者从尾走到头。但二叉树不一样它一上来就要求你“自己调用自己”。很多新手第一次写递归函数脑子里想的还是“这个函数调用到什么时候是个头”结果一写就死循环一调试就栈溢出。我给你打一个比方。你在公司里要把一份通知传达到每个工位可以挨个走一遍这是循环。但如果是让每个收到通知的人再转发给坐在他旁边的人这就是递归。二叉树的前序、中序、后序遍历本质上都是“先访问自己再让左子树转发再让右子树转发”这种模式。你要做的不是把整棵树的操作顺序在脑子里完整走一遍而是只负责“当前节点”这一步剩下的事交给递归调用。我见过太多人卡在遍历题上不是因为不会写代码而是因为总想“一口气想清楚整棵树的执行过程”这会让大脑直接过载。正确的做法是把递归当成一个黑盒你只要确认两点第一当前这一步处理得对不对第二边界条件写对没有。剩下的交给函数自己。说得再直白一点二叉树题就是“递归思维”的第一场大考这一关过了后面的树形DP、搜索、平衡树才有基础。1.2 OJ题和教材例题差了不止一个“输入输出”教材里讲二叉树通常是给你一棵画好的树然后讲遍历序列怎么来的。你照着图能看懂但一上OJ题目根本不会给你一棵树它给你的是输入数据。不同OJ、不同题目的输入格式五花八门有的是让你根据先序序列建树空节点用特殊字符表示有的是给你两个数组让你重建二叉树还有的是直接用数组下标模拟完全二叉树。华为OJ牛客网上的华为机试和东华OJ上最常见的二叉树题基本都是“给定一个序列建树然后求深度、遍历、判定”。GESP六级也特别喜欢考满二叉树和二叉搜索树的概念题。你要是只会“对着图数节点”不会写建树和输入解析上了OJ照样拿不到分。所以我在这篇文章里不止讲“遍历怎么写”还会把建树的常见套路、输入处理的细节、边界条件的坑一起讲清楚。这些才是你做OJ题真正需要的部分。2. 二叉树基础概念先过一遍“代码视角”的结构定义2.1 结构体定义指针还是数组你得先有个谱在OJ题里二叉树的节点定义C/C几乎固定长这样struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };如果你用的是C那就写成普通结构体加typedeftypedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode;这个结构体本身不复杂但有两个细节值得注意。第一左右孩子指针一定要初始化。很多新手在写建树代码的时候new一个节点出来只赋了val没有把left和right置空结果遍历的时候遇到一个野指针程序直接崩溃OJ反馈“段错误”。你在自己的机器上跑可能碰巧没崩一提交就崩原因就在这里。C的构造函数里写left(nullptr), right(nullptr)就是这个作用。第二如果你不想用指针完全可以用数组模拟。对于完全二叉树或者满二叉树用数组存特别方便下标为i的节点左孩子下标是2i右孩子下标是2i1。很多GESP六级的题目尤其是和满二叉树相关的都喜欢给数组表示法因为这类树的形态就是“层序填满”的数组天然契合。2.2 建树与销毁OJ里也会考察的“隐藏操作”OJ题里建树一般有两种场景。一种是你自己写代码从输入序列里建树另一种是题目已经封装好了TreeNode结构你只需要写核心函数。但不管哪种建树本身都是基本功。最常见的建树方式是用先序序列加空标记。比如输入1 2 # # 3 4 # # #代表树的结构是1的左孩子是22没有左右孩子1的右孩子是33的左孩子是44没有左右孩子3的右孩子为空。这种格式在OJ里非常常见。建树代码通常长这样TreeNode* buildTree() { string val; cin val; if (val #) return nullptr; TreeNode* root new TreeNode(stoi(val)); root-left buildTree(); root-right buildTree(); return root; }注意这个函数是“先读当前值再递归建左子树再递归建右子树”顺序不能乱。如果题目给的是层序序列那你得用队列来建树不能用递归。这也是很多新手容易踩的坑。至于销毁树OJ通常不会检查内存泄漏因为程序跑完就结束了但如果你在做一些内存要求严格的题目或者想养成好习惯可以写一个递归释放函数void freeTree(TreeNode* root) { if (!root) return; freeTree(root-left); freeTree(root-right); delete root; }这里一定要先递归删左右子树再删自己。顺序反了你先把root释放掉再去访问root-left就是访问野指针了。3. 必刷题型一四种遍历递归和迭代两手抓3.1 递归遍历把代码写到不能再短二叉树的先序、中序、后序遍历递归写法几乎一样唯一区别就是访问根节点的那行代码放在哪个位置void preorder(TreeNode* root) { if (!root) return; cout root-val ; preorder(root-left); preorder(root-right); } void inorder(TreeNode* root) { if (!root) return; inorder(root-left); cout root-val ; inorder(root-right); } void postorder(TreeNode* root) { if (!root) return; postorder(root-left); postorder(root-right); cout root-val ; }这三段代码建议你抄下来反复默写写到肌肉记忆为止。因为它们在后面的搜索二叉树、表达式树、线索二叉树题目里都会反复出现。递归遍历的关键在于理解“顺序”是怎么产生的。拿中序遍历来说它先访问左子树再访问自己再访问右子树。如果你把一棵搜索二叉树做中序遍历得到的结果一定是从小到大有序的。这个性质后面做题会用到。我建议新手在学这一步的时候一定要亲手在纸上画一棵三层高的树把递归调用的顺序模拟一遍。不用多画三棵就够了。这个过程能帮你把“递归返回”这件事彻底想明白。3.2 迭代遍历栈和队列才是OJ考察重点很多OJ题会明确要求“用迭代完成遍历”理由是递归有栈溢出风险而且考试的时候有些题目的确会用极端数据卡你的递归深度。比如一棵退化成链状的树深度可能是10万层递归直接爆栈。先序遍历的迭代写法用栈就够了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; }这里有个细节先序顺序是“根-左-右”但因为栈是后进先出所以你要先把右孩子压栈再压左孩子。这样左孩子会先出栈访问。这个顺序搞反了输出就变成“根-右-左”了。中序遍历的迭代写法稍微绕一点因为它要“先走到最左边”再一路回溯vectorint inorderTraversal(TreeNode* root) { vectorint res; stackTreeNode* st; TreeNode* cur root; while (cur || !st.empty()) { while (cur) { st.push(cur); cur cur-left; } cur st.top(); st.pop(); res.push_back(cur-val); cur cur-right; } return res; }这个模板你一定要吃透。它模拟的是“一路向左走到头然后回退一步再走向右子树”的过程。我见过很多人在这里卡住其实只要记住一句话先把所有左孩子全部压栈然后逐个弹出每次弹出后把当前节点的右孩子设为下一个要处理的节点。你就永远不会写错。后序迭代最取巧的办法是“先序反过来”。先序遍历是根-左-右那如果你把压栈顺序反过来变成根-右-左再把结果反转就是左-右-根也就是后序遍历vectorint postorderTraversal(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-left) st.push(node-left); if (node-right) st.push(node-right); } reverse(res.begin(), res.end()); return res; }这个方法虽然不算正统的“迭代后序遍历”但OJ题只认结果不认过程。你用它就能AC为什么要跟自己做对呢当然如果题目要求你必须用标准后序迭代那再额外学一种写法也不迟。3.3 层序遍历广度优先的入门模板层序遍历就是一层一层从上往下遍历这在很多题目里都会用到比如求二叉树最大宽度、判断完全二叉树、输出每一层的节点。它的核心数据结构是队列vectorvectorint levelOrder(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; }注意那个int size q.size();这是层序遍历的模板灵魂。它记录的是“当前这一层有多少个节点”。你必须在处理这一层之前先记录这个数因为后面push子节点的时候q.size()会变。如果你直接写for (int i 0; i q.size(); i)就会出现一层没遍历完、队列又塞进了新节点的情况输出就乱了。这四个遍历模板建议你全部在本地跑通然后去OJ找三道对应的题目练手。我当时就是靠把四套模板背得滚瓜烂熟后面遇到带“遍历”两个字的题心态都很稳。4. 必刷题型二二叉树深度、节点数、叶子节点数4.1 最大深度和最小深度别被“最小深度”坑了二叉树的深度问题是OJ的高频题几乎每个OJ系统里都能搜到“求二叉树深度”的题目。递归写法很简单int maxDepth(TreeNode* root) { if (!root) return 0; return 1 max(maxDepth(root-left), maxDepth(root-right)); }这个代码很多人一眼就看懂了但其实里面藏着一个思维陷阱递归函数返回的是“以当前节点为根的子树深度”。空节点深度是0非空节点深度是1加上左右子树深度的最大值。你只要始终站在“当前节点”的角度想这个函数就不难理解。最小深度稍微坑一点。先看很多人写的第一版int minDepth(TreeNode* root) { if (!root) return 0; return 1 min(minDepth(root-left), minDepth(root-right)); }这个代码在“根节点只有左子树没有右子树”的情况下会算错。比如一棵树1的左孩子是2右孩子是null那么真实的“从根到最近叶子节点的距离”应该是2也就是路径1-2。但上面的代码会返回1min(0, 1)1因为minDepth(root-left)0导致结果变成1。正确的写法是int minDepth(TreeNode* root) { if (!root) return 0; if (!root-left) return 1 minDepth(root-right); if (!root-right) return 1 minDepth(root-left); return 1 min(minDepth(root-left), minDepth(root-right)); }也就是说当一边子树缺失时你不能拿0和另一边比因为“0”不代表叶子节点只代表空。新手容易忽视这个边界条件结果提交之后WA测试用例明明就是最简单的树却找不出错。这就是典型的“递归边界意识”没建立起来。4.2 节点统计类题目的通用递归模板求节点总数、求叶子节点数、求第k层节点数这些题本质上都是“遍历时计数”。我建议你记住这个通用模板int countNodes(TreeNode* root) { if (!root) return 0; return 1 countNodes(root-left) countNodes(root-right); }求叶子节点数只要把“当前节点没有左右孩子时返回1”这个条件加进去int countLeaves(TreeNode* root) { if (!root) return 0; if (!root-left !root-right) return 1; return countLeaves(root-left) countLeaves(root-right); }这种题刷多了你会发现一个规律递归函数通常把问题拆成“当前节点 左子树的答案 右子树的答案”。你用这个思路去套几乎所有的统计类问题都不会差太多。但这里有一个很现实的问题如果树的深度特别大递归会爆栈。有些OJ题的数据范围就是十万级深度这时候你要么用迭代栈模拟递归要么用“全局计数器遍历”的方式避免深层返回链。比如求节点总数你可以用层序遍历每弹出一个节点就计数这样根本不存在递归深度问题。5. 必刷题型三搜索二叉树与满二叉树判定5.1 搜索二叉树BST判定只比左小右大一定会漏搜索二叉树Binary Search Tree也叫二叉排序树是二叉树里非常重要的一个子类型。它的定义是左子树所有节点的值小于根节点右子树所有节点的值大于根节点并且左右子树也分别是BST。很多新手一看这个定义就写下了这样的代码bool isValidBST(TreeNode* root) { if (!root) return true; if (root-left root-left-val root-val) return false; if (root-right root-right-val root-val) return false; return isValidBST(root-left) isValidBST(root-right); }表面上看它检查了当前节点的左右孩子也递归检查了子树。但问题在于它只检查了“左孩子小于父节点”没有检查“左子树的所有节点都小于父节点”。比如下面这棵树5 / \ 1 6 / \ 4 7这里6的左孩子是4满足46但这棵树不是BST因为4在根节点5的右子树里却小于5。正确的判定方法有两种。第一种是“上下界传递法”每个节点都带一个允许的取值范围(min, max)左子节点的所有值必须在(min, root-val)之间右子节点的所有值必须在(root-val, max)之间。bool help(TreeNode* root, long long lower, long long upper) { if (!root) return true; if (root-val lower || root-val upper) return false; return help(root-left, lower, root-val) help(root-right, root-val, upper); } bool isValidBST(TreeNode* root) { return help(root, LLONG_MIN, LLONG_MAX); }注意用long long做边界因为题目经常出INT_MIN和INT_MAX的边界值直接用int会判断错误。第二种方法就是中序遍历判断有序。BST中序遍历结果一定是严格递增的所以你可以先做中序遍历得到一个数组再检查数组是否有序。这个方法更好理解但要多开O(n)空间。我推荐前一种方法因为它是真正的递归判定且不需要额外数组。5.2 满二叉树与完全二叉树概念不能混判定套路要记牢最近GESP六级、东华OJ的题目里二叉树的“形态判定”出现频率挺高。满二叉树Full Binary Tree和完全二叉树Complete Binary Tree长得像但定义完全不同新手经常混淆。满二叉树如果一棵二叉树的每个节点要么是叶子节点要么有两个孩子那么它就是满二叉树。注意这里每个非叶子节点都必须有两个孩子叶子节点都在同一层。在层序序列里满二叉树的节点数一定是2^n - 1n是层数。完全二叉树若二叉树只有最下面两层的节点度数可以小于2且最下面一层的叶子节点都依次排列在最左边则称完全二叉树。满二叉树一定是完全二叉树但反过来不一定。判定满二叉树除了数节点数还有一个直观的方法层序遍历遇到任何一个节点只有单个孩子就不是满二叉树。或者递归判断每个节点要么没有孩子要么有两个孩子bool isFullTree(TreeNode* root) { if (!root) return true; if (!root-left !root-right) return true; if (root-left root-right) return isFullTree(root-left) isFullTree(root-right); return false; }判定完全二叉树最经典的方法是用层序遍历加“空标记”。思路是层序遍历时把空节点也放进去。如果遇到了空节点之后后面还出现了非空节点那就不是完全二叉树。bool isCompleteTree(TreeNode* root) { if (!root) return true; queueTreeNode* q; q.push(root); bool hasGap false; while (!q.empty()) { TreeNode* node q.front(); q.pop(); if (!node) { hasGap true; } else { if (hasGap) return false; q.push(node-left); q.push(node-right); } } return true; }这里的核心原理是完全二叉树在层序遍历序列里所有空节点一定集中在最后。如果出现“空节点之后又有非空节点”说明在这一层还没填满的情况下就已经出现了空位不符合完全二叉树要求。这两种判定题其实考察的是你对树的“形状”有没有准确的建模能力。刷题的时候不要死记代码要理解为什么这样判。6. 常见问题与排查技巧这些坑我替你踩过了6.1 递归边界错位的三种典型症状二叉树递归题最容易犯的错误就是边界条件写错而且错误往往有固定的“症状”。我总结了三种最常见的你以后遇到直接对号入座。第一种忘记判空。比如maxDepth里你不写if (!root) return 0;函数会一直访问空指针的成员直接段错误。解决办法就是凡是入口处先判空这几乎是二叉树递归题的“安全呼吸法则”了。第二种返回值类型和递归含义不一致。比如有人写“求深度”的递归函数却把返回值定义成void然后用全局变量记录最大值。这种写法也能AC但很容易在下一道题翻车因为你没有建立好“递归函数返回子问题的解”这个抽象。第三种统计类问题重复计算。求节点总数时如果写成countNodes(root) countNodes(root-left) countNodes(root-right)会把当前节点算两次。我见过有新手在两个OJ题上栽过跟头就是这种低级错误。解决办法很简单写递归之前先在心里把“当前节点、左子树、右子树”三者的关系用一句话说出来然后再转化成代码。6.2 空指针和栈溢出问题排查二叉树OJ题最常见的运行时错误是Segmentation Fault段错误排查起来也很痛苦。我的习惯是三步走。第一步检查建树部分。输入解析有没有正确读到数据空节点有没有被正确识别为nullptr而不是被当成0存进节点值。第二步检查递归调用顺序。凡是访问node-left或node-right之前一定要先确认node不是nullptr。特别是层序遍历里你往队列里push了node-left下一次循环取出来时它可能就被pop之前被别的代码释放了这种情况比较少见但如果你自己写了freeTree就要格外小心。第三步如果数据规模很大就用“静态数组下标模拟树”的方式代替指针。很多OJ题给的是完全二叉树你可以直接用数组模拟根本不用递归也就没有爆栈问题。栈溢出Stack Overflow在OJ里一般表现为“程序异常退出”或者“运行时错误”而且通常在大数据量时才出现。如果你确认算法没问题第一反应就应该是把递归改成迭代。6.3 OJ提交的实用建议输入、输出与多组数据这里我想专门说一说OJ提交的细节因为很多新手代码逻辑没问题却在输入输出上栽了跟头。第一题目要求多组输入时你的代码要写成“循环处理”的模式比如int main() { string s; while (cin s) { // 建树、处理、输出 } return 0; }很多题目没说“多组数据”但测试文件里面就是有多组你不写while循环就只能过第一组后面全WA。第二输出格式要严格按照题目要求。比如每个结果后面要求一个空格还是换行最后一组之后允不允许输出换行这些细节决定你是AC还是PE格式错误。PE虽然不算完全错但笔试考试中也会扣分。第三建议用引用传参或全局变量优化不要在每个测试用例里都重新new一整棵树然后delete。有些OJ平台内存卡得紧频繁new/delete不仅慢还容易产生内存碎片。更稳妥的做法是每个case结束后手动释放或者直接用静态数组和下标节点。7. 关于二叉树刷题的几条个人经验二叉树刷题到后面拼的其实是两点递归理解的深度和建立模型的速度。我个人从刷第一道二叉树遍历题时的抓狂到后来基本扫一眼题目就能在脑子里画出递归树中间主要靠的是两件事一是把上面的基础题型反复默写不是背代码而是默写“递归函数在做什么”二是遇到WA先打印中间结果而不是盯着代码干瞪眼。最后分享一个我到现在还在用的小技巧遇到二叉树题目先假设它是一棵只有三个节点的最小树根、左孩子、右孩子在纸上把逻辑跑一遍。如果这个最小场景能跑通再扩展到五层树。很多边界错误在最小场景下会立刻现形。这个方法帮我在东华OJ和牛客网的华为题单上省下了大量调试时间也建议你试试。