从前序与中序遍历构造二叉树

Leetcode Link: 105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode） (leetcode-cn.com)

题目

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

提示:

• 1 <= preorder.length <= 3000
• inorder.length == preorder.length
• -3000 <= preorder[i], inorder[i] <= 3000
• preorder 和 inorder 均 无重复 元素
• inorder 均出现在 preorder
• preorder 保证为二叉树的前序遍历序列
• inorder 保证 为二叉树的中序遍历序列

解法一

思路：主要思想是将问题分解成左右子树上的子问题，在每个节点上，我们需要找到这个节点的左子树范围，右子树范围，然后送到递归构建其左右子树。

给定前序、中序的顺序，可以通过前序中序的特点得知位置 主要的难点在于，如何确定左右子树的区间（假设我们在前序序列上找左右子树的区间），对于一个区间，我们给出的两端的端点，都默认含左不含右（左开右闭）

题解：

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if len(preorder) == 0:
            return None
        def recur(pre_start, pre_end, in_start, in_end):
			# 区间重合，说明没有节点了，直接返回 None
			# 开始的时候自己还设定了两者差为1的返回，此时返回一个TreeNode(val=preorder[pre_start])，后来发现多次一举
            if (pre_end-pre_start)==0:
                return None
			# 头节点为前序的第一个
            cur_val = preorder[pre_start]
            # 找到中序中头节点的位置
            in_root_ind = inorder.index(cur_val)
			# 创建当前节点
            cur_node = TreeNode(val=cur_val)
			# 当前节点的在 preorder 上的左子树范围为[pre_start+1, pre_start+1+in_root_ind-in_start)
			# 其尾端点计算利用了中序中计算的左子树长度 in_root_ind-in_start
			# 当前节点的在 inorder 上的右子树范围为[in_start, in_root_ind)，简单
            cur_node.left = recur(pre_start+1,pre_start+1+in_root_ind-in_start,
                                 in_start, in_root_ind) 
            # 利用中序计算长度，思路同上
            cur_node.right = recur(pre_start+1+in_root_ind-in_start,pre_end, in_root_ind + 1, in_end)
            return cur_node
        return recur(0, len(preorder), 0, len(inorder))
 
 

启发和联系

在以后的代码中，如果有遇到区间端点的问题，最好都指定左闭右开