- POJ 2255 - Tree Recovery
- Time: 1000MS
- Memory: 65536K
- 难度: 初级
- 分类: 图遍历
问题描述
二叉树遍历：给定前序和中序，求后序。
解题思路
见代码注释。
AC 源码
/*
Author: Exp
Date: 2017-12-01
Code: POJ 2255
Problem: Tree Recovery
URL: http://poj.org/problem?id=2255
*/
/*
题意分析：
给出一棵二叉树的前序遍历与中序遍历，求后序遍历.
其中二叉树由不重复的大写字母组成，每个节点一个字母.
解题思路：
① 前序遍历的第一个字母必是 根
② 在中序遍历的字母串中找出 根字母，那么根字母左右两边的字符串就分别是它的左、右子树
③ 由于树的最大深度只有26，因此可以不考虑堆栈溢出，利用[递归]结合①②复原二叉树
④ 对复原的二叉树使用DFS做后序遍历即可
注：
对二叉树的 前序遍历、中序遍历、后序遍历 均可以使用DFS来做，
均是自上而下、自左至右遍历，区别在于打印节点的时机不同：
[前序遍历] 从父节点进入时打印当前节点
[中序遍历] 从左子树返回时打印当前节点
[后序遍历] 从右子树返回时打印当前节点
*/
#include <memory.h>
#include <iostream>
using namespace std;
const static int STR_LEN = 27; // 树遍历序列最大长度
const static char NULL_CHAR = '\0'; // 空字符
// 节点结构
class Node {
public:
char name; // 节点名称
Node* left; // 左子树根节点
Node* right; // 右子树根节点
Node(): name(NULL_CHAR), left(NULL), right(NULL) {}
~Node() {
name = NULL_CHAR;
delete left; left = NULL;
delete right; right = NULL;
}
};
/*
* 根据前序序列与中序序列还原二叉树
* @param preOrder 前序遍历序列
* @param inOrder 中序遍历序列
* return 所构造树的根节点
*/
Node* createTree(char* preOrder, char* inOrder);
/*
* DFS遍历树，构造后序序列
* @param root 树根节点
* @param _out_postOrder 后序序列
*/
void dfs(Node* root, char* _out_postOrder);
int main(void) {
char preOrder[STR_LEN] = { NULL_CHAR };
char inOrder[STR_LEN] = { NULL_CHAR };
while(cin >> preOrder >> inOrder) {
Node* root = createTree(preOrder, inOrder); // 构造二叉树
char postOrder[STR_LEN] = { NULL_CHAR }; // 后序序列
dfs(root, postOrder); // DFS遍历树，生成后序序列
cout << postOrder << endl;
delete root;
memset(preOrder, NULL_CHAR, sizeof(char) * STR_LEN);
memset(inOrder, NULL_CHAR, sizeof(char) * STR_LEN);
}
return 0;
}
Node* createTree(char* preOrder, char* inOrder) {
const int LEN = strlen(preOrder);
if(LEN <= 0) {
return NULL;
}
Node* root = new Node();
root->name = *preOrder; // 前序遍历的第一个节点必定是树根
char* leftPreOrder = new char[LEN + 1]; // 左子树前序列
char* leftInOrder = new char[LEN + 1]; // 左子树中序列
char* rigntPreOrder = new char[LEN + 1]; // 右子树前序列
char* rigntInOrder = new char[LEN + 1]; // 右子树中序列
// 使左/右子树的前/中序列与根节点的树序列一直，后面再根据根节点的位置进行序列截取
strcpy(leftPreOrder, preOrder);
strcpy(leftInOrder, inOrder);
strcpy(rigntPreOrder, preOrder);
strcpy(rigntInOrder, inOrder);
// 根据根节点在中序序列的位置，调整左右子树的前序序列和中序序列范围
for(int i = 0; *(inOrder + i) != NULL_CHAR; i++) {
if(root->name == *(inOrder + i)) {
*(leftInOrder + i) = NULL_CHAR; // 标记左子树[中序序列]的结束点
int leftLen = strlen(leftInOrder); // 左子树节点数
*(leftPreOrder + leftLen + 1) = NULL_CHAR; // 标记左子树[前序序列]的结束点
Node* leftTree = createTree((leftPreOrder + 1), leftInOrder); // 生成左子树
Node* rightTree = createTree(
(rigntPreOrder + leftLen + 1), (rigntInOrder + i + 1)); // 生成右子树
root->left = leftTree;
root->right = rightTree;
break;
}
}
// 注：前面在标记左/右子树序列的起始位置时，不能变更数组指针地址，否则这里无法释放内存
delete[] leftPreOrder;
delete[] leftInOrder;
delete[] rigntPreOrder;
delete[] rigntInOrder;
return root;
}
void dfs(Node* root, char* _out_postOrder) {
if(root == NULL) {
return;
}
dfs(root->left, _out_postOrder);
dfs(root->right, _out_postOrder);
// 构造后序序列：从右子树返回时把当前节点名称放到序列末尾
*(_out_postOrder + strlen(_out_postOrder)) = root->name;
}
