【二叉树】已经中序和后序，构建一个二叉树
已经中序(infix)和后序(postfix)，重新构建一个二叉树在剑指office看到的题目，代码放在这里用作记录
中序：4、7、2、1、5、3、8、6
后序：7、4、2、5、8、6、3、1
0、输入的个数为length
1、记录后序最后一个结点的值post_infix（根结点）。如：根为1
2、找到中序的该结点位置下标root_index（从0开始），下标数字也表示当前根结点的左子树全部结点个数。如：根为1的中序root_index=3
3、递归找postfixroot_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(右子树)的根结点，片段的长度为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
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)
root_index=0
while root_index<length:
if infix==postfix:
break
root_index+=1
print(temp.val,end=' ')
if length>1:
temp.left=create(postfix,infix,root_index)
temp.right=create(postfix,infix,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=
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
页:
[1]