举一反三

前序+中序

class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        # write code here
        if len(pre)>0:
            root = TreeNode(pre[0])
            root_idx = tin.index(pre[0])
            root.left = self.reConstructBinaryTree(pre[1:1+root_idx],
                                                   tin[:root_idx])
            root.right = self.reConstructBinaryTree(pre[1+root_idx:],
                                                    tin[root_idx+1:])
            return root

后序+中序

class Solution1:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, post, tin):
        # write code here
        if len(post)>0:
            root = TreeNode(post[-1])#后序遍历的倒数第一个节点是根节点
            root_idx = tin.index(post[-1])
            root.left = self.reConstructBinaryTree(post[:root_idx],tin[:root_idx])
            root.right = self.reConstructBinaryTree(post[root_idx:-1],tin[root_idx+1:])
            return root

层序+中序

class Solution:
     def buildtree(self,level,mid):
        if len(level)>0:
            root=TreeNode(level[0])#根节点
            rootid=mid.index(level[0])
            midleft=mid[:rootid]#左子树包含的节点
            midright=mid[rootid+1:]#右子树包含的节点
            levelleft,levelright=[],[]
            for node in level:
                if node in midleft:
                    levelleft.append(node)
                if node in midright:
                    levelright.append(node)
            root.left=self.buildtree(levelleft,midleft)
            root.right=self.buildtree(levelright,midright)
            return root