408 每日一题 Day 2：二叉树的重构与遍历

一、题目描述

已知一棵二叉树的前序遍历序列为ABDECFG，中序遍历序列为DBEAFCG，则该二叉树的后序遍历序列是？

• A.DEBFGCA
• B.DEBFCGA
• C.DEBFGAC
• D.DEBFAGC

二、考点分析

三、前置知识回顾

3.1 二叉树的三种遍历方式

3.2 核心结论

给定前序 + 中序，可以唯一确定一棵二叉树。

• 前序：确定根节点
• 中序：确定左右子树的节点范围

3.3 判断方法速记

四、解题思路

4.1 基本步骤

1. 从前序遍历序列中取出第一个节点，它就是当前子树的根节点
2. 在中序遍历序列中找到根节点的位置
3. 中序中根节点左边的所有节点属于左子树，右边的所有节点属于右子树
4. 根据左子树和右子树的节点个数，从前序中划分出左右子树的前序序列
5. 递归处理左右子树

五、手动还原过程

5.1 已知序列

前序：A B D E C F G 中序：D B E A F C G

5.2 第一步：确定根节点

前序第一个节点是A，所以根节点是A。

在中序中找到A的位置：

中序：D B E | A | F C G 左子树 右子树

• 左子树节点：D, B, E（共 3 个）
• 右子树节点：F, C, G（共 3 个）

5.3 第二步：处理左子树

左子树节点有 3 个：D, B, E

在前序中，根A后面的 3 个节点就是左子树的前序序列：

• 左子树前序：B D E

左子树中序：D B E

对左子树递归：

• 前序B D E的第一个节点是B，所以左子树的根是B
• 在中序D B E中找到B：
  • 左边：D→ 左子树的左子树
  • 右边：E→ 左子树的右子树

所以：

• B的左孩子是D
• B的右孩子是E

5.4 第三步：处理右子树

右子树节点有 3 个：F, C, G

在前序中，左子树用掉 3 个节点后，剩下的就是右子树的前序：

• 右子树前序：C F G

右子树中序：F C G

对右子树递归：

• 前序C F G的第一个节点是C，所以右子树的根是C
• 在中序F C G中找到C：
  • 左边：F→ 右子树的左子树
  • 右边：G→ 右子树的右子树

所以：

• C的左孩子是F
• C的右孩子是G

5.5 第四步：画出整棵树

A / \ B C / \ / \ D E F G

5.6 第五步：求后序遍历

后序遍历顺序：左子树 → 右子树 → 根

• 左子树B的后序：D E B
• 右子树C的后序：F G C
• 整棵树的后序：D E B+F G C+A=D E B F G C A

验证选项：DEBFGCA对应选项 A。

答案：A

六、代码实现

6.1 根据前序和中序重构二叉树

#include<iostream>#include<string>#include<unordered_map>usingnamespacestd;structTreeNode{charval;TreeNode*left;TreeNode*right;TreeNode(charx):val(x),left(nullptr),right(nullptr){}};classSolution{private:unordered_map<char,int>inorderIndex;// 记录中序中每个值的位置string preorder,inorder;TreeNode*build(intpreStart,intpreEnd,intinStart,intinEnd){if(preStart>preEnd)returnnullptr;charrootVal=preorder[preStart];TreeNode*root=newTreeNode(rootVal);introotIndex=inorderIndex[rootVal];// 根在中序中的位置intleftSize=rootIndex-inStart;// 左子树的节点个数// 递归构建左子树和右子树root->left=build(preStart+1,preStart+leftSize,inStart,rootIndex-1);root->right=build(preStart+leftSize+1,preEnd,rootIndex+1,inEnd);returnroot;}public:TreeNode*buildTree(string pre,string in){preorder=pre;inorder=in;for(inti=0;i<in.size();i++){inorderIndex[in[i]]=i;}returnbuild(0,pre.size()-1,0,in.size()-1);}};

6.2 后序遍历输出

voidpostorder(TreeNode*root){if(!root)return;postorder(root->left);postorder(root->right);cout<<root->val;}intmain(){string pre="ABDECFG";string in="DBEAFCG";Solution s;TreeNode*root=s.buildTree(pre,in);cout<<"后序遍历结果: ";postorder(root);// 输出: DEBFGCAcout<<endl;return0;}

6.3 复杂度分析

七、相关题目推荐

八、总结