[华为机试练习题]10.二叉树遍历

题目

描述:
二叉树的前序、中序、后序遍历的定义：
前序遍历：对任一子树，先访问跟，然后遍历其左子树，最后遍历其右子树；
中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树；
后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。
给定一棵二叉树的前序遍历和中序遍历，求其后序遍历（提示：给定前序遍历与中序遍历能够唯一确定后序遍历）。

题目类别: 树
难度: 中级
运行时间限制: 无限制
内存限制: 无限制
阶段: 入职前练习
输入:
两个字符串，其长度n均小于等于26。
第一行为前序遍历，第二行为中序遍历。
二叉树中的结点名称以大写字母表示：A，B，C….最多26个结点。

输出:
输入样例可能有多组，对于每组测试样例，
输出一行，为后序遍历的字符串。

样例输入:
ABC
BAC
FDXEAG
XDEFAG

样例输出:
BCA
XEDGAF

代码

/*---------------------------------------
*   日期：2015-06-29
*   作者：SJF0115
*   题目：二叉树遍历
*   来源：华为上机
-----------------------------------------*/
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

struct TreeNode{
    char val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(char x):val(x),left(NULL),right(NULL){}
};

TreeNode* PreInBuildTree(string preorder,string inorder,int preIndex,int inIndex,int size){
    if(size <= 0){
        return NULL;
    }//if
    // 根节点
    TreeNode* root = new TreeNode(preorder[preIndex]);
    // 寻找根节点在中序遍历数组的下标
    int index = 0;
    for(int i = 0;i < size;++i){
        // 注意：inorder[inIndex+i]
        if(preorder[preIndex] == inorder[inIndex+i]){
            index = inIndex+i;
            break;
        }//if
    }//for
    // 左子树个数
    int leftSize = index - inIndex;
    // 右子树个数
    int rightSize = size - leftSize - 1;
    // 左子树
    root->left = PreInBuildTree(preorder,inorder,preIndex+1,inIndex,leftSize);
    // 右子树
    root->right = PreInBuildTree(preorder,inorder,preIndex+1+leftSize,index+1,rightSize);
    return root;
}

TreeNode *buildTree(string preorder,string inorder){
    int size = preorder.size();
    if(size <= 0){
        return NULL;
    }//if
    return PreInBuildTree(preorder,inorder,0,0,size);
}

void PostOrder(TreeNode* root){
    if(root){
        PostOrder(root->left);
        PostOrder(root->right);
        cout<<root->val;
    }//if
}

int main(){
    string preStr,inStr;
    //freopen("C:\\Users\\Administrator\\Desktop\\c++.txt","r",stdin);
    while(cin>>preStr>>inStr){
        TreeNode* root = buildTree(preStr,inStr);
        PostOrder(root);
        cout<<endl;
    }//while
    return 0;
}