根据两种遍历来构建二叉树

本题目只是以中序后序遍历作为例子，其他的两种也是一样的。

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        ### 构建辅助函数
        def helper(inorder, postorder, inorder_left, inorder_right, postorder_left, postorder_right):
            ### 空
            if inorder_left > inorder_right:
                return None
             
            ### 根据遍历的特点，先找到根，重建树
            root = TreeNode(postorder[postorder_right])  ### 构造树
            if postorder_left == postorder_right:  ### 如果只有根节点，就直接返回结果
                return root
            
            local = inorder.index(postorder[postorder_right])  ### 在中序遍历中寻找root的位置
            size = local - inorder_left  ### 判断左子树长度

            root.left = helper(inorder, postorder, inorder_left, local-1, postorder_left, postorder_left+size-1) ### 这个二叉树在中后遍历中左子树的长度需要计算清楚，千万不能包括根节点。
            ### 如果左子树只有一个，那么这个是inorder_left=local-1
            root.right = helper(inorder, postorder, local+1, inorder_right, postorder_left+size, postorder_right-1)
            return root
        return helper(inorder, postorder, 0, len(inorder)-1, 0, len(postorder)-1)

本文地址：https://blog.csdn.net/gwy2018/article/details/107372002