# -*- coding: utf-8 -*-
import sys
class BTree:
'''
Represent a no in a binary tree.
'''
def __init__(self, c='/0', l=None, r=None):
'''
Initializes the node's data
'''
self.e = c
self.left = l
self.right = r
def preorderTraverse(bt):
'''
返回前序遍历结果
'''
if bt:
return '%s%s%s' % (bt.e, preorderTraverse(bt.left), preorderTraverse(bt.right))
return ''
def inorderTraverse(bt):
'''
返回中序遍历结果
'''
if bt:
return '%s%s%s' % (inorderTraverse(bt.left), bt.e, inorderTraverse(bt.right))
return '';
def postorderTraverse(bt):
'''
返回后序遍历结果
'''
if bt:
return '%s%s%s' % (postorderTraverse(bt.left), postorderTraverse(bt.right), bt.e)
return ''
def printBTree(bt, depth):
'''
递归打印这棵二叉树,*号表示该节点为NULL
'''
'''
if not bt:
ch = '*'
else:
ch = bt.e
'''
#ch=(lambda x: (x and x.e) or '*')(bt)
ch = bt.e if bt else '*'
if(depth > 0):
print '%s%s%s' % ((depth - 1) * ' ', '--', ch)
else:
print ch
if not bt:
return
printBTree(bt.left, depth + 1)
printBTree(bt.right, depth + 1)
def buildBTreeFromPreIn(preo, ino):
'''
根据前序和中序遍历结果重构这棵二叉树
'''
if(preo == '' or ino == ''):
return None
pos = ino.find(preo[0])
if(pos < 0):
return None
return BTree(preo[0], buildBTreeFromPreIn(preo[1:pos + 1], ino[0:pos]), buildBTreeFromPreIn(preo[pos + 1:], ino[pos + 1:]))
Alist = []
for line in sys.stdin:
a = line.split()[0]
Alist.append(a)
if len(Alist) == 2:
preo,ino = Alist[0],Alist[1]
bt = buildBTreeFromPreIn(preo, ino)
print postorderTraverse(bt)
Alist=[]
/**************************************************************
Problem: 2193
User: admin
Language: Python
Result: Wrong Answer
****************************************************************/