题解 | #牛群的树形结构重建#

• 题目考察的知识点 : 中序遍历和后序遍历构造二叉树
• 题目解答方法的文字分析：

1. 后序遍历的最后一个元素为整棵树的根节点；
2. 在中序遍历中找到根节点的位置，左边为左子树的中序遍历，右边为右子树的中序遍历；
3. 根据左子树的中序遍历长度，确定后序遍历中左右子树的分界点；
4. 递归地构造左右子树，返回根节点。

• 本题解析所用的编程语言: Python
• 完整且正确的编程代码

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param inOrder int整型一维数组 
# @param postOrder int整型一维数组 
# @return TreeNode类
#
class Solution:
    def buildTree(self , inOrder: List[int], postOrder: List[int]) -> TreeNode:
        if not inOrder or not postOrder:
            return None

        root_val = postOrder[-1]
        root_idx = inOrder.index(root_val)

        left_inorder = inOrder[:root_idx]
        right_inorder = inOrder[root_idx+1:]

        left_postorder = postOrder[:len(left_inorder)]
        right_postorder = postOrder[len(left_inorder):-1]

        root = TreeNode(root_val)
        root.left = self.buildTree(left_inorder, left_postorder)
        root.right = self.buildTree(right_inorder, right_postorder)

        return root