TOJ2801--Binary Trees

제목

입력은 약간 특별한 두 갈래 나무의 뒷순서가 흐르는 문자열입니다.그 중에서 문자열의 소문자는 잎 노드이고 대문자는 비잎 노드이다.그리고 이 나무의 중순을 출력하기;input
2 bcA efBghCA
output
bAc eBfAgCh

생각

그때 할 때 한마디도 주의하지 않았다.
Given the post-order traversal of a binary tree, each of whose non-leaf nodes has exactly two children
이 말은 완전히 두 갈래 나무라는 것을 설명한다...그 결과 오랫동안 고민하여 두 갈래 나무의 제목을 만들었다. 일반적인 사고방식은 뿌리를 찾고 왼쪽 나무를 찾고 오른쪽 나무를 찾은 다음에 왼쪽 나무를 찾고 오른쪽 나무를 찾는 것이다.이것도 고려할 수 있다. 현재 트리를 세 부분으로 나눈다. left root right 뒤에 흐르는 마지막 문자는 틀림없이 root 부분이다.그리고 완전 두 갈래 나무이기 때문에 모든 비잎 노드에는 반드시 두 명의 아이가 있고 한 그루의 나무에는 좌우 나무에는 대문자가 소문자보다 하나 적다.이곳은 좌우 나무를 갈라낼 수 있다.한 가지 주의해야 할 것은 거꾸로 수색해야 한다는 것이다. 완전히 두 갈래 나무의 왼쪽 나무에 박힌 하위 나무도 조건이 충족되기 때문에 오른쪽 하위 나무 부분을 먼저 찾아야 한다.

코드

/*Accepted 2801 C++ 0.5K 0'00.02" 1352K */
#include <iostream>
#include <string>
using namespace std;
int T;
string s;
string in_order(string s)
{
    int len=s.length(),n=0,i;
    if (len==1)return s;//   
    for(i=len-2;i>=0;i--)
    {//   ： 
        if(s[i]>='a'&&s[i]<='z')n++;
        else n--;
        if(n==1) break;
    }
    return in_order(s.substr(0,i))+s.substr(len-1,1)+in_order(s.substr(i,len-i-1));
}
int main()
{
    cin>>T;
    while(T--)
    {
      cin>>s;
      cout<<in_order(s)<<endl;
    }
}

전체 트리를 만든 후 출력에서 순서를 정하는 코드를 첨부합니다. 핵심은 같습니다.

/*Accepted 2801 C++ 1.1K 0'00.01" 1616K */
#include <iostream>
using namespace std;

struct TreeNode{
    TreeNode *left;
    TreeNode *right;
    char ch;
};

TreeNode * createTree(TreeNode *root,string s)
{// 
    int len=s.length(),i=0,n=0;

    root=new TreeNode();
    root->ch=s[len-1];
    root->left=root->right=NULL;
    if(len==1) return root;// 

    for(i=len-2;i>=0;i--)
    {
        if(s[i]>='a'&&s[i]<='z') n++;
        else n--;
        if(n==1) break;
    }
    root->left=createTree(root->left,s.substr(0,i));
    root->right=createTree(root->right,s.substr(i,len-i-1));
    return root;
}
void inOrder(TreeNode *root)
{// 
    if(!root) return;
    inOrder(root->left);
    cout<<root->ch;
    inOrder(root->right);

}
void del(TreeNode *root)
{
    if(!root) return;
    if(!root->left&&!root->right)
    {
        delete(root);
        return;
    }
    del(root->left);
    del(root->right);
}
int main()
{
    int T;
    string s;
    cin>>T;
    while(T--)
    {
        cin>>s;
        TreeNode *root;
        root=createTree(root,s);
        inOrder(root);
        cout<<'
';
        del(root);
    }
}