1896: 扩展二叉树
Memory Limit:256 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
由于先序、中序和后序序列中的任一个都不能唯一确定一棵二叉树,所以对二叉树做如下处理,将二叉树的空结点用·补齐,如图所示。我们把这样处理后的二叉树称为原二叉树的扩展二叉树,扩展二叉树的先序和后序序列能唯一确定其二叉树。
![](data:image/png;base64,R0lGODlhXwCJAPcAAAAAAAAAMwAAZgAAmQAAzAAA/wArAAArMwArZgArmQArzAAr/wBVAABVMwBVZgBVmQBVzABV/wCAAACAMwCAZgCAmQCAzACA/wCqAACqMwCqZgCqmQCqzACq/wDVAADVMwDVZgDVmQDVzADV/wD/AAD/MwD/ZgD/mQD/zAD//zMAADMAMzMAZjMAmTMAzDMA/zMrADMrMzMrZjMrmTMrzDMr/zNVADNVMzNVZjNVmTNVzDNV/zOAADOAMzOAZjOAmTOAzDOA/zOqADOqMzOqZjOqmTOqzDOq/zPVADPVMzPVZjPVmTPVzDPV/zP/ADP/MzP/ZjP/mTP/zDP//2YAAGYAM2YAZmYAmWYAzGYA/2YrAGYrM2YrZmYrmWYrzGYr/2ZVAGZVM2ZVZmZVmWZVzGZV/2aAAGaAM2aAZmaAmWaAzGaA/2aqAGaqM2aqZmaqmWaqzGaq/2bVAGbVM2bVZmbVmWbVzGbV/2b/AGb/M2b/Zmb/mWb/zGb//5kAAJkAM5kAZpkAmZkAzJkA/5krAJkrM5krZpkrmZkrzJkr/5lVAJlVM5lVZplVmZlVzJlV/5mAAJmAM5mAZpmAmZmAzJmA/5mqAJmqM5mqZpmqmZmqzJmq/5nVAJnVM5nVZpnVmZnVzJnV/5n/AJn/M5n/Zpn/mZn/zJn//8wAAMwAM8wAZswAmcwAzMwA/8wrAMwrM8wrZswrmcwrzMwr/8xVAMxVM8xVZsxVmcxVzMxV/8yAAMyAM8yAZsyAmcyAzMyA/8yqAMyqM8yqZsyqmcyqzMyq/8zVAMzVM8zVZszVmczVzMzV/8z/AMz/M8z/Zsz/mcz/zMz///8AAP8AM/8AZv8Amf8AzP8A//8rAP8rM/8rZv8rmf8rzP8r//9VAP9VM/9VZv9Vmf9VzP9V//+AAP+AM/+AZv+Amf+AzP+A//+qAP+qM/+qZv+qmf+qzP+q///VAP/VM//VZv/Vmf/VzP/V////AP//M///Zv//mf//zP///wAAAAAAAAAAAAAAACH5BAEAAPwALAAAAABfAIkAAAj/APcJHEiwoMGDCBMqXMiwocOHECNKnEixosWLGDNq3Mixo8ePIEOKHEmypMmTKFOqXMmypcuXMGPKnEmzps2bIwHoxElSJwCeInfuBPpR6E+iHo0i7Th0X9OlGJs+hWrRp1WqUY8OnIo14lSuXcPC1Cr24k+yZSVKTTsRrVO2EN0KlAvXIN25dROCLXiXbV++eQn+tRv4rdq8g/X6TayQsU3HCyHLlFyY6VWgVvfG1ao5plTKgkG3/FxVNEvSFTs/zmzW9ErUFFXXhN3WtUratbfazsl5N2vMvzPuRjk8NNSzG5Ej5azxaPGQZIs7x0w46lacdG1Hv9nXNdrnyRtX/wVMc7Bpt+DNOgSd3XPcwwfTt/UKP75L9vQRyn94nn/kytUpRtxlmxE43klDycaXY7Ip2Fxvm63nU2MTloRbZIwZaFeFPUHIX3D6mbdfiLpFmNaFFC5W4ocqOiWZg9hp2FBmI/ak3one1ZiTYfPpGBRe8/FIFXNBCrkUkfldd5xgRQJ5JHnvQUnUd0lKiV2A6wnIE3pVWjmbfv6Jd6V9Wf7HHZhlmlmemGq2ORmbcLr50l/dgRifjKfJadyMHt43o16JwYjgnyQyJOhxgfpooqF30QjoXBymhOeCeyn41KHJRRpipYnu+VqGjYK6Yot8aupXl3C9WNihmF4JWatnMljo5ImzmqmojUayeeuPtWq5K0jbEdrrkEwKO+xyXqKpZFdcGorlkskm+2tzZMa57JPPVhvtmNluO+2B2oYr1n6wIhhqineW2yFYk+I5qWemusgpp1Oe+yiAE/jmq+++/Pbr778AByzwwAQTFBAAOw==)
现给出扩展二叉树的先序序列,要求输出其中序和后序序列。
现给出扩展二叉树的先序序列,要求输出其中序和后序序列。
Input
扩展二叉树的先序序列。
Output
输出其中序和后序序列。
Sample Input Copy
ABD..EF..G..C..
Sample Output Copy
DBFEGAC
DFGEBCA