# -*- 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:])) for line in sys.stdin: preo,ino = line.split() #print preo,ino bt = buildBTreeFromPreIn(preo, ino) print postorderTraverse(bt) /************************************************************** Problem: 2121 User: admin Language: Python Result: Wrong Answer ****************************************************************/