【二叉树】已经中序和后序，构建一个二叉树

Lthero

已经中序(infix)和后序(postfix)，重新构建一个二叉树

在剑指office看到的题目，代码放在这里用作记录


中序：4、7、2、1、5、3、8、6
后序：7、4、2、5、8、6、3、1

0、输入的个数为length
1、记录后序最后一个结点的值post_infix[length-1]（根结点）。如：根为1
2、找到中序的该结点位置下标root_index（从0开始），下标数字也表示当前根结点的左子树全部结点个数。如：根为1的中序root_index=3
3、递归找postfix[0:root_index](左子树)的根结点，片段的长度为root_index。如：找下标从【0~2】的根结点，长度length变为root_index=3
中序：4、7、2、1、5、3、8、6
后序：7、4、2、5、8、6、3、1
4、递归找postfix[root_index:](右子树)的根结点，片段的长度为length-root_index-1。如：找下标从【3~length-1】的根结点，片段的长度length变为4
中序：4、7、2、1、5、3、8、6
后序：7、4、2、5、8、6、3、1

[Python] 纯文本查看 复制代码

?

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

class TreeNode:     def __init__(self, x):         self.val = x         self.left = None         self.right = None   def create(postfix,infix,length):     if length==0:         return None     temp=TreeNode(postfix[length-1])     root_index=0     while root_index<length:         if infix[root_index]==postfix[length-1]:             break         root_index+=1     print(temp.val,end=' ')     if length>1:         temp.left=create(postfix,infix,root_index)         temp.right=create(postfix[root_index:],infix[root_index+1:],length-root_index-1)     else:         temp.left=None         temp.right=None     return temp       postfix=input('输入后序').split(' ') infix=input('输入中序').split(' ') length=len(infix) print('-------------前序输出----------------') root=create(postfix,infix,length) print('\n-------------层序输出----------------') queue=[root] while len(queue)!=0:     x=queue.pop(0)     print(x.val,end=' ')     if x.left is not None:         queue.append(x.left)     if x.right is not None:         queue.append(x.right)   #H M I D N J E B K F G C A #H D M I B J N E A F K C G