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

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] 纯文本查看 复制代码

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