题解 | #二叉树遍历#

#include <iostream>
using namespace std;
// 给定：前序和中序， 构建树后， 给出后序遍历序列。 
struct TreeNode 
{
    TreeNode * left ; 
    TreeNode * right ; 
    char elem ; 
    TreeNode(char c ) : elem(c) , left(nullptr) , right(nullptr) {} ; 
}; 
TreeNode * build(string s1 , string s2)
{
    if(s1.size() == 0 && s2.size() == 0)
    {
        return nullptr;  
    }
    int i = 0 ; 
    char c = s1[i]  ; 
    TreeNode * root = new  TreeNode(c) ; 
    string l1 , l2 ; 
    while(s2[i] != c)
    {
        l1+= s2[i] ;  // 左子树的中序序列
        i++ ; // 
    }
    i++ ; 
    while(i < s2.size())
    {
        l2 += s2[i] ;  // 右子树的中序序列 
        i++ ; 
    }
    // 依据中序 找 前序
    i = 1 ; 
    string r1 , r2 ; 
    for(int t = 0; t < l1.size() ; ++ t)// 按照数量相等去找到。 
    {
        r1 += s1[i] ; 
        i++ ; 
    }
    for(int t = 0 ;t < l2.size() ; ++ t )
    {
        r2 += s1[i] ; 
        i++ ; 
    }
    root->left = build(r1 , l1 ) ;  // 左子树
    root->right = build(r2 , l2 ) ;  // 右子树 
    return root ; 
}
void postorder(TreeNode * cur)
{
    if(cur == nullptr)
    {
        return ; 
    }
    
    postorder(cur->left) ; 
    postorder(cur->right) ; 
    cout<<cur->elem ; 
}
int main() {
    string s1 , s2 ; 
while(cin>>s1) // 前序序列。 
{
    cin>>s2  ; // 中序序列
    TreeNode * root = build(s1, s2 ) ; 
    postorder(root) ; 
    cout<<endl ;  
}
}
// 64 位输出请用 printf("%lld")