思路:
递归并正确分割前序和中序序列
前序分割为左子树和右子树,左子树的开头是第二个数,中间包含节点的数量为中序从0到根节点的数量
所以是pre[1:tin.index(pre[0])+1]
右子树是剩下的部分
同理,中序左子树是从左边到根节点的部分,tin[:tin.index(pre[0])]
递归
def reConstructBinaryTree(self, pre, tin): # write code here if len(pre)==0: return None if len(pre)==1: return TreeNode(pre[0]) root=TreeNode(pre[0]) tinL=tin[:tin.index(pre[0])] tinR=tin[tin.index(pre[0])+1:] root.left=self.reConstructBinaryTree(pre[1:tin.index(pre[0])+1],tinL) root.right=self.reConstructBinaryTree(pre[tin.index(pre[0])+1:],tinR) return root