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

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

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

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

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

        root_val = preOrder[0]
        root_idx = inOrder.index(root_val)

        left_preorder = preOrder[1:root_idx+1]
        right_preorder = preOrder[root_idx+1:]

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

        root = TreeNode(root_val)
        root.left = self.buildTreeII(left_preorder, left_inorder)
        root.right = self.buildTreeII(right_preorder, right_inorder)

        return root