企业官网建设流程全解析

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，那就写成普通结构体加typedef：

typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode;

这个结构体本身不复杂，但有两个细节值得注意。

第一，左右孩子指针一定要初始化。很多新手在写建树代码的时候，new一个节点出来只赋了val，没有把left和right置空，结果遍历的时候遇到一个野指针，程序直接崩溃，OJ反馈“段错误”。你在自己的机器上跑，可能碰巧没崩，一提交就崩，原因就在这里。C++的构造函数里写left(nullptr), right(nullptr)就是这个作用。

第二，如果你不想用指针，完全可以用数组模拟。对于完全二叉树或者满二叉树，用数组存特别方便：下标为i的节点，左孩子下标是2i，右孩子下标是2i+1。很多GESP六级的题目，尤其是和满二叉树相关的，都喜欢给数组表示法，因为这类树的形态就是“层序填满”的，数组天然契合。

2.2 建树与销毁：OJ里也会考察的“隐藏操作”

OJ题里建树一般有两种场景。一种是你自己写代码，从输入序列里建树；另一种是题目已经封装好了TreeNode结构，你只需要写核心函数。但不管哪种，建树本身都是基本功。

最常见的建树方式是用先序序列加空标记。比如输入1 2 # # 3 4 # # #，代表树的结构是1的左孩子是2，2没有左右孩子，1的右孩子是3，3的左孩子是4，4没有左右孩子，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万层，递归直接爆栈。

先序遍历的迭代写法，用栈就够了：

vector<int> preorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> 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; }

这里有个细节：先序顺序是“根-左-右”，但因为栈是后进先出，所以你要先把右孩子压栈，再压左孩子。这样左孩子会先出栈访问。这个顺序搞反了，输出就变成“根-右-左”了。

中序遍历的迭代写法稍微绕一点，因为它要“先走到最左边”，再一路回溯：

vector<int> inorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> 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; }

这个模板你一定要吃透。它模拟的是“一路向左走到头，然后回退一步，再走向右子树”的过程。我见过很多人在这里卡住，其实只要记住一句话：先把所有左孩子全部压栈，然后逐个弹出，每次弹出后把当前节点的右孩子设为下一个要处理的节点。你就永远不会写错。

后序迭代最取巧的办法是“先序反过来”。先序遍历是根-左-右，那如果你把压栈顺序反过来，变成根-右-左，再把结果反转，就是左-右-根，也就是后序遍历：

vector<int> postorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> 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 层序遍历：广度优先的入门模板

层序遍历就是一层一层从上往下遍历，这在很多题目里都会用到，比如求二叉树最大宽度、判断完全二叉树、输出每一层的节点。它的核心数据结构是队列：

vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> res; if (!root) return res; queue<TreeNode*> q; q.push(root); while (!q.empty()) { int size = q.size(); vector<int> 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。但上面的代码会返回1+min(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，满足4<6，但这棵树不是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 - 1（n是层数）。
• 完全二叉树：若二叉树只有最下面两层的节点度数可以小于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; queue<TreeNode*> 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和牛客网的华为题单上省下了大量调试时间，也建议你试试。