【Leetcode刷题】从前序与中序遍历序列构造二叉树

题目：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution:
    # preorder的组成：[root, <左树的所有元素>, <右树的所有元素>]
    # inorder的组成：[ <左树的所有元素>, root, <右树的所有元素>]
    # preorder的第一个元素既是root
    # 在inorder中定位root，root左边的元素既是左子树的所有元素，右边的元素既是右子树的所有元素
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        # tree_preorder, tree_inorder表示子树的前序遍历和中序遍历
        def get_tree(tree_preorder, tree_inorder):
            # 空树
            if not tree_preorder:
                return None
            root = tree_preorder[0]
            node = TreeNode(root)
            # 只有一个元素，不需要再求左右子树
            if len(tree_preorder) == 1:
                return node
            root_index = tree_inorder.index(root)
            # 切片操作是浅拷贝，因此不用担心浪费内存的问题
            # 取到左数的所有元素
            left_inorder = tree_inorder[:root_index]
            left_count = len(left_inorder)
            # preorder的组成：[root, <左树的所有元素>, <右树的所有元素>]
            node.left = get_tree(tree_preorder[1: left_count+1], left_inorder)
            node.right = get_tree(tree_preorder[left_count+1:], tree_inorder[root_index+1:])
            return node
        return get_tree(preorder, inorder)

优化：不需要用len(left_inorder)来求元素的数量，root_index就是左数元素的数量了。

class Solution:
    # preorder的组成：[root, <左树的所有元素>, <右树的所有元素>]
    # inorder的组成：[ <左树的所有元素>, root, <右树的所有元素>]
    # preorder的第一个元素既是root
    # 在inorder中定位root，root左边的元素既是左子树的所有元素，右边的元素既是右子树的所有元素
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        # tree_preorder, tree_inorder表示子树的前序遍历和中序遍历
        def get_tree(tree_preorder, tree_inorder):
            # 空树
            if not tree_preorder:
                return None
            root = tree_preorder[0]
            node = TreeNode(root)
            # 只有一个元素，不需要再求左右子树
            if len(tree_preorder) == 1:
                return node
            root_index = tree_inorder.index(root)
            # 切片操作是浅拷贝，因此不用担心浪费内存的问题
            node.left = get_tree(tree_preorder[1: root_index+1], tree_inorder[:root_index])
            node.right = get_tree(tree_preorder[root_index+1:], tree_inorder[root_index+1:])
            return node
        return get_tree(preorder, inorder)