1.洛谷 P4913 二叉树深度递归写法详细解析这道题本质就是一个非常经典的二叉树问题给你一棵树的结构让你求从根节点到最远叶子节点的最大层数也就是我们常说的“树的深度”。题目中给出的输入其实已经帮我们把树“存好了”每个节点 i 都会告诉你它的左孩子和右孩子是谁如果是 0 就说明没有孩子并且根节点固定为 1所以我们只需要从 1 出发一层一层往下算即可。这类题最直接、最符合直觉的方法就是递归因为树本身就是一种递归结构——一个节点的深度取决于它左右子树的深度所以思路可以很自然地写成当前节点的深度 左子树深度 和 右子树深度 的最大值 1。对应到代码就是这样一段核心函数int getdepth(int node) { if (node 0) return 0; int leftdepth getdepth(leftchild[node]); int rightdepth getdepth(rightchild[node]); return max(leftdepth, rightdepth) 1; }这里有几个细节是必须理解的首先为什么 node 0 要返回 0因为 0 表示这个节点不存在也就是空树而空树的深度就是 0其次为什么最后要 1因为当前这个节点本身也要算一层比如一个叶子节点它左右都是 0那么深度就是 max(0,0)1 1再一个就是为什么要取 max因为题目要求的是“最大深度”也就是走最远的那一条路径。整道题的数据规模最大可以到 10^6所以我们用数组来存储树结构是非常合理的leftchild[i] 表示 i 的左孩子rightchild[i] 表示右孩子这样查找是 O(1)整体效率很高。完整代码如下可以直接运行#includeiostream using namespace std; const int MAXN 1e6 5; int leftchild[MAXN]; int rightchild[MAXN]; int n; int getdepth(int node) { if (node 0) return 0; int leftdepth getdepth(leftchild[node]); int rightdepth getdepth(rightchild[node]); return max(leftdepth, rightdepth) 1; } int main() { cin n; for (int i 1; i n; i) { cin leftchild[i] rightchild[i]; } int ans getdepth(1); cout ans; return 0; }这段代码的执行过程其实可以理解为“从根节点一路往下探”每走到一个节点就继续往它的左右孩子递归直到走到叶子节点再一层一层返回在返回的过程中不断取最大值最终得到整棵树的最大深度。时间复杂度是 O(n)因为每个节点只访问一次空间复杂度主要来自递归栈在最坏情况下树退化成一条链会达到 O(n)也就是说如果数据非常极端是有可能出现栈溢出的不过在大多数正常数据下是没问题的递归过程图解一定要搞懂这一部分很多人写这道题的时候其实代码会写但对递归是“怎么跑的”并不清楚这一段我用一棵简单的树把整个过程一步一步讲清楚。我们用下面这棵树来演示1 / \ 2 7 / \ 3 6 / 4我们调用的是getdepth(1);程序一开始不会直接算出答案而是会先去“问子节点”也就是说它会先去算左子树再算右子树可以理解为getdepth(1) ├── getdepth(2) └── getdepth(7)接下来程序会优先一直往左走也就是不断递归下去getdepth(2) ├── getdepth(3) └── getdepth(6) getdepth(3) ├── getdepth(4) └── getdepth(0) getdepth(4) ├── getdepth(0) └── getdepth(0)注意这里已经走到最底部了节点 4 的左右孩子都是 0说明它是叶子节点这时候递归不能再往下了就开始“返回结果”。首先返回的是节点 4getdepth(4) max(0, 0) 1 1然后把结果带回给上一层也就是节点 3getdepth(3) max(1, 0) 1 2接着处理节点 6它是叶子节点getdepth(6) max(0, 0) 1 1再回到节点 2getdepth(2) max(2, 1) 1 3左子树算完之后程序才会去算右子树也就是节点 7getdepth(7) max(0, 0) 1 1最后回到根节点 1整棵树的答案也就出来了getdepth(1) max(3, 1) 1 4整个过程如果用一句话总结就是先一路往下递归把问题不断拆小再从最底层开始一层一层返回结果最终在根节点得到答案。很多人容易误以为递归是在“从上往下算”其实不是真正的计算发生在“回来的时候”也就是从叶子节点开始往上合并结果这就是递归在树问题中的核心思想。2.洛谷 P1305 新二叉树前序遍历 递归详解这道题本质就是二叉树的基础操作给你一棵用字符表示的二叉树结构让你输出它的前序遍历结果相比普通数组建树这道题的特点是用字符作为节点并且用*表示空节点。题目输入的每一行其实就是在描述一棵树的“父子关系”第一个字符是当前节点后两个字符分别是它的左孩子和右孩子比如abc就表示 a 的左孩子是 b右孩子是 c如果是d**说明 d 是叶子节点。这里我们用unordered_mapchar, pairchar, char来存树结构意思就是通过一个节点可以快速找到它的左右孩子这种写法比数组更灵活也更适合字符节点的题目。整道题的核心其实就是“前序遍历”所谓前序遍历就是先访问当前节点再访问左子树最后访问右子树。对应的递归写法非常简单也非常经典void preorder(char node) { if (node *) { return; } cout node; preorder(tree[node].first); preorder(tree[node].second); }这里有两个关键点需要注意第一为什么遇到*要直接 return因为*表示空节点相当于不存在第二访问顺序一定是当前节点 → 左子树 → 右子树这个顺序一旦写错结果就完全不一样。程序的执行过程其实和你上一题“求深度”的递归非常像也是先一路往下递归再一层一层返回只不过这次不是“计算值”而是“输出路径”。我们用样例简单走一遍abc bdi cj* d** i** j**这棵树结构大概是a / \ b c / \ \ d i j递归调用过程可以理解为先从 a 开始输出 a然后进入左子树 b输出 b继续进入 d输出 d发现 d 没有孩子就返回再回到 b进入 i输出 i再返回到 a进入右子树 c输出 c最后输出 j。所以最终输出就是abdicj完整代码如下可以直接运行#includeiostream #includeunordered_map using namespace std; int n; unordered_mapchar, pairchar, char tree; void preorder(char node) { if (node *) { return; } cout node; preorder(tree[node].first); preorder(tree[node].second); } int main() { cin n; char root; for (int i 1; i n; i) { char parent, left, right; cin parent left right; tree[parent] { left, right }; if (i 1) { root parent; } } preorder(root); return 0; }时间复杂度是 O(n)因为每个节点只访问一次空间复杂度主要来自递归调用栈最坏情况下是 O(n)。这道题其实是“树遍历”的入门题掌握之后你可以顺带学习另外两种遍历方式中序遍历和后序遍历它们的区别本质就是“访问当前节点的位置不同”一旦理解递归这三种写法都是一行改一行的事情。最后总结一句话前序遍历就是“先自己再左再右”只要记住这个顺序这类题基本不会出错。3.#includeiostream using namespace std; void getpreorder(string inorder, string postorder) { if (inorder.empty()) return; char root postorder.back(); cout root; int rootpos inorder.find(root); string leftinorder inorder.substr(0, rootpos); string leftpostorder postorder.substr(0,leftinorder.size()); getpreorder(leftinorder, leftpostorder); string rightinorder inorder.substr(rootpos 1); string rightpostorder postorder.substr(leftinorder.size(),rightinorder.size()); getpreorder(rightinorder, rightpostorder); } int main() { string inorder, postorder; cin inorder postorder; getpreorder(inorder, postorder); return 0; }洛谷 P1030 求先序排列中序 后序 推前序详解这道题是二叉树里一个非常经典的“反推问题”已知中序遍历和后序遍历让你还原出先序遍历节点数量不大≤8但思路非常重要是树这一块的核心知识之一。先说结论这题本质就一句话后序确定根中序划分左右递归构建。我们先快速回顾三种遍历的特点前序是“根 → 左 → 右”中序是“左 → 根 → 右”后序是“左 → 右 → 根”这里最关键的是后序遍历的最后一个节点一定是整棵树的根。比如样例中序BADC 后序BDCA后序最后一个字符是 A所以 A 一定是整棵树的根节点。接下来我们去中序序列里找 A可以把中序分成两部分中序 B | A | DC ↑ 根左边B是左子树右边DC是右子树这一步非常关键相当于把树“切开了”。接下来要做的是在后序序列中把左右子树对应的部分也切出来因为后序是“左 → 右 → 根”所以去掉最后一个 A 后后序BDC前面一部分是左子树后面一部分是右子树左子树有几个节点看中序左边的长度这里左边是B长度是 1所以左子树后序B 右子树后序DC这样一来我们就把问题拆成了两个子问题接下来对左右子树继续做同样的事情这就是递归。你的代码正是按照这个思路写的void getpreorder(string inorder, string postorder) { if (inorder.empty()) return; char root postorder.back(); // 后序最后一个是根 cout root; int rootpos inorder.find(root); string leftinorder inorder.substr(0, rootpos); string leftpostorder postorder.substr(0, leftinorder.size()); getpreorder(leftinorder, leftpostorder); string rightinorder inorder.substr(rootpos 1); string rightpostorder postorder.substr(leftinorder.size(), rightinorder.size()); getpreorder(rightinorder, rightpostorder); }这里每一步其实都对应一个明确的含义postorder.back() 找根find(root) 在中序里定位substr 切出左右子树然后递归处理。我们把整个过程完整走一遍会更清楚。第一步确定根节点后序最后一个是 A输出 A。第二步划分中序B | A | DC左子树是 B右子树是 DC。第三步划分后序去掉 A 后是 BDC左子树长度是 1所以左是 B右是 DC。第四步递归左子树中序B后序B根是 B输出 B。第五步递归右子树中序DC后序DC根是 C输出 C再继续拆中序D | C 后序D | C根是 C左子树是 D继续递归输出 D。最终输出顺序是A B C D也就是ABCD这正是先序遍历根 → 左 → 右。整个过程你可以这样理解我们不是在“构建整棵树”而是在“边拆边输出”利用遍历的性质一步一步把结构还原出来。时间复杂度是 O(n^2)因为每次 find 都要线性查找但 n 很小所以完全没问题如果数据更大可以用哈希表优化到 O(n)。最后总结一句话后序找根中序分树递归处理输出顺序就是先序。
【数据结构与算法】二叉树做题做题做题
发布时间：2026/5/27 15:55:39
1.洛谷 P4913 二叉树深度递归写法详细解析这道题本质就是一个非常经典的二叉树问题给你一棵树的结构让你求从根节点到最远叶子节点的最大层数也就是我们常说的“树的深度”。题目中给出的输入其实已经帮我们把树“存好了”每个节点 i 都会告诉你它的左孩子和右孩子是谁如果是 0 就说明没有孩子并且根节点固定为 1所以我们只需要从 1 出发一层一层往下算即可。这类题最直接、最符合直觉的方法就是递归因为树本身就是一种递归结构——一个节点的深度取决于它左右子树的深度所以思路可以很自然地写成当前节点的深度 左子树深度 和 右子树深度 的最大值 1。对应到代码就是这样一段核心函数int getdepth(int node) { if (node 0) return 0; int leftdepth getdepth(leftchild[node]); int rightdepth getdepth(rightchild[node]); return max(leftdepth, rightdepth) 1; }这里有几个细节是必须理解的首先为什么 node 0 要返回 0因为 0 表示这个节点不存在也就是空树而空树的深度就是 0其次为什么最后要 1因为当前这个节点本身也要算一层比如一个叶子节点它左右都是 0那么深度就是 max(0,0)1 1再一个就是为什么要取 max因为题目要求的是“最大深度”也就是走最远的那一条路径。整道题的数据规模最大可以到 10^6所以我们用数组来存储树结构是非常合理的leftchild[i] 表示 i 的左孩子rightchild[i] 表示右孩子这样查找是 O(1)整体效率很高。完整代码如下可以直接运行#includeiostream using namespace std; const int MAXN 1e6 5; int leftchild[MAXN]; int rightchild[MAXN]; int n; int getdepth(int node) { if (node 0) return 0; int leftdepth getdepth(leftchild[node]); int rightdepth getdepth(rightchild[node]); return max(leftdepth, rightdepth) 1; } int main() { cin n; for (int i 1; i n; i) { cin leftchild[i] rightchild[i]; } int ans getdepth(1); cout ans; return 0; }这段代码的执行过程其实可以理解为“从根节点一路往下探”每走到一个节点就继续往它的左右孩子递归直到走到叶子节点再一层一层返回在返回的过程中不断取最大值最终得到整棵树的最大深度。时间复杂度是 O(n)因为每个节点只访问一次空间复杂度主要来自递归栈在最坏情况下树退化成一条链会达到 O(n)也就是说如果数据非常极端是有可能出现栈溢出的不过在大多数正常数据下是没问题的递归过程图解一定要搞懂这一部分很多人写这道题的时候其实代码会写但对递归是“怎么跑的”并不清楚这一段我用一棵简单的树把整个过程一步一步讲清楚。我们用下面这棵树来演示1 / \ 2 7 / \ 3 6 / 4我们调用的是getdepth(1);程序一开始不会直接算出答案而是会先去“问子节点”也就是说它会先去算左子树再算右子树可以理解为getdepth(1) ├── getdepth(2) └── getdepth(7)接下来程序会优先一直往左走也就是不断递归下去getdepth(2) ├── getdepth(3) └── getdepth(6) getdepth(3) ├── getdepth(4) └── getdepth(0) getdepth(4) ├── getdepth(0) └── getdepth(0)注意这里已经走到最底部了节点 4 的左右孩子都是 0说明它是叶子节点这时候递归不能再往下了就开始“返回结果”。首先返回的是节点 4getdepth(4) max(0, 0) 1 1然后把结果带回给上一层也就是节点 3getdepth(3) max(1, 0) 1 2接着处理节点 6它是叶子节点getdepth(6) max(0, 0) 1 1再回到节点 2getdepth(2) max(2, 1) 1 3左子树算完之后程序才会去算右子树也就是节点 7getdepth(7) max(0, 0) 1 1最后回到根节点 1整棵树的答案也就出来了getdepth(1) max(3, 1) 1 4整个过程如果用一句话总结就是先一路往下递归把问题不断拆小再从最底层开始一层一层返回结果最终在根节点得到答案。很多人容易误以为递归是在“从上往下算”其实不是真正的计算发生在“回来的时候”也就是从叶子节点开始往上合并结果这就是递归在树问题中的核心思想。2.洛谷 P1305 新二叉树前序遍历 递归详解这道题本质就是二叉树的基础操作给你一棵用字符表示的二叉树结构让你输出它的前序遍历结果相比普通数组建树这道题的特点是用字符作为节点并且用*表示空节点。题目输入的每一行其实就是在描述一棵树的“父子关系”第一个字符是当前节点后两个字符分别是它的左孩子和右孩子比如abc就表示 a 的左孩子是 b右孩子是 c如果是d**说明 d 是叶子节点。这里我们用unordered_mapchar, pairchar, char来存树结构意思就是通过一个节点可以快速找到它的左右孩子这种写法比数组更灵活也更适合字符节点的题目。整道题的核心其实就是“前序遍历”所谓前序遍历就是先访问当前节点再访问左子树最后访问右子树。对应的递归写法非常简单也非常经典void preorder(char node) { if (node *) { return; } cout node; preorder(tree[node].first); preorder(tree[node].second); }这里有两个关键点需要注意第一为什么遇到*要直接 return因为*表示空节点相当于不存在第二访问顺序一定是当前节点 → 左子树 → 右子树这个顺序一旦写错结果就完全不一样。程序的执行过程其实和你上一题“求深度”的递归非常像也是先一路往下递归再一层一层返回只不过这次不是“计算值”而是“输出路径”。我们用样例简单走一遍abc bdi cj* d** i** j**这棵树结构大概是a / \ b c / \ \ d i j递归调用过程可以理解为先从 a 开始输出 a然后进入左子树 b输出 b继续进入 d输出 d发现 d 没有孩子就返回再回到 b进入 i输出 i再返回到 a进入右子树 c输出 c最后输出 j。所以最终输出就是abdicj完整代码如下可以直接运行#includeiostream #includeunordered_map using namespace std; int n; unordered_mapchar, pairchar, char tree; void preorder(char node) { if (node *) { return; } cout node; preorder(tree[node].first); preorder(tree[node].second); } int main() { cin n; char root; for (int i 1; i n; i) { char parent, left, right; cin parent left right; tree[parent] { left, right }; if (i 1) { root parent; } } preorder(root); return 0; }时间复杂度是 O(n)因为每个节点只访问一次空间复杂度主要来自递归调用栈最坏情况下是 O(n)。这道题其实是“树遍历”的入门题掌握之后你可以顺带学习另外两种遍历方式中序遍历和后序遍历它们的区别本质就是“访问当前节点的位置不同”一旦理解递归这三种写法都是一行改一行的事情。最后总结一句话前序遍历就是“先自己再左再右”只要记住这个顺序这类题基本不会出错。3.#includeiostream using namespace std; void getpreorder(string inorder, string postorder) { if (inorder.empty()) return; char root postorder.back(); cout root; int rootpos inorder.find(root); string leftinorder inorder.substr(0, rootpos); string leftpostorder postorder.substr(0,leftinorder.size()); getpreorder(leftinorder, leftpostorder); string rightinorder inorder.substr(rootpos 1); string rightpostorder postorder.substr(leftinorder.size(),rightinorder.size()); getpreorder(rightinorder, rightpostorder); } int main() { string inorder, postorder; cin inorder postorder; getpreorder(inorder, postorder); return 0; }洛谷 P1030 求先序排列中序 后序 推前序详解这道题是二叉树里一个非常经典的“反推问题”已知中序遍历和后序遍历让你还原出先序遍历节点数量不大≤8但思路非常重要是树这一块的核心知识之一。先说结论这题本质就一句话后序确定根中序划分左右递归构建。我们先快速回顾三种遍历的特点前序是“根 → 左 → 右”中序是“左 → 根 → 右”后序是“左 → 右 → 根”这里最关键的是后序遍历的最后一个节点一定是整棵树的根。比如样例中序BADC 后序BDCA后序最后一个字符是 A所以 A 一定是整棵树的根节点。接下来我们去中序序列里找 A可以把中序分成两部分中序 B | A | DC ↑ 根左边B是左子树右边DC是右子树这一步非常关键相当于把树“切开了”。接下来要做的是在后序序列中把左右子树对应的部分也切出来因为后序是“左 → 右 → 根”所以去掉最后一个 A 后后序BDC前面一部分是左子树后面一部分是右子树左子树有几个节点看中序左边的长度这里左边是B长度是 1所以左子树后序B 右子树后序DC这样一来我们就把问题拆成了两个子问题接下来对左右子树继续做同样的事情这就是递归。你的代码正是按照这个思路写的void getpreorder(string inorder, string postorder) { if (inorder.empty()) return; char root postorder.back(); // 后序最后一个是根 cout root; int rootpos inorder.find(root); string leftinorder inorder.substr(0, rootpos); string leftpostorder postorder.substr(0, leftinorder.size()); getpreorder(leftinorder, leftpostorder); string rightinorder inorder.substr(rootpos 1); string rightpostorder postorder.substr(leftinorder.size(), rightinorder.size()); getpreorder(rightinorder, rightpostorder); }这里每一步其实都对应一个明确的含义postorder.back() 找根find(root) 在中序里定位substr 切出左右子树然后递归处理。我们把整个过程完整走一遍会更清楚。第一步确定根节点后序最后一个是 A输出 A。第二步划分中序B | A | DC左子树是 B右子树是 DC。第三步划分后序去掉 A 后是 BDC左子树长度是 1所以左是 B右是 DC。第四步递归左子树中序B后序B根是 B输出 B。第五步递归右子树中序DC后序DC根是 C输出 C再继续拆中序D | C 后序D | C根是 C左子树是 D继续递归输出 D。最终输出顺序是A B C D也就是ABCD这正是先序遍历根 → 左 → 右。整个过程你可以这样理解我们不是在“构建整棵树”而是在“边拆边输出”利用遍历的性质一步一步把结构还原出来。时间复杂度是 O(n^2)因为每次 find 都要线性查找但 n 很小所以完全没问题如果数据更大可以用哈希表优化到 O(n)。最后总结一句话后序找根中序分树递归处理输出顺序就是先序。
