105. 从前序与中序遍历序列构造二叉树
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
题目解析
题目解答
对于任意一颗树而言，前序遍历的形式总是
[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]
即根节点总是前序遍历中的第一个节点。而中序遍历的形式总是
[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]
只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。由于同一颗子树的前序遍历和中序遍历的长度显然是相同的，因此我们就可以对应到前序遍历的结果中，对上述形式中的所有左右括号进行定位。
这样以来，我们就知道了左子树的前序遍历和中序遍历结果，以及右子树的前序遍历和中序遍历结果，我们就可以递归地对构造出左子树和右子树，再将这两颗子树接到根节点的左右位置。
代码展示
# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution:def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:# step 1 : 判空if not preorder or not inorder:return# step 2：以 前序遍历 第一个点 作为 根root = TreeNode(preorder[0])# step 3：获取根节点 在 中序遍历 中的位置idx = inorder.index(preorder[0])# step 4：构建左子树root.left = self.buildTree(preorder[1:1 + idx], inorder[:idx])# step 5：构建右子树root.right = self.buildTree(preorder[1 + idx:], inorder[idx + 1:])return root
复杂度计算
时间复杂度 O(N)：当树退化为链表时（全部为右子节点），无论 k 的值大小，递归深度都为 N ，占用 O(N) 时间。
空间复杂度 O(N) ：当树退化为链表时（全部为右子节点），系统使用 O(N)大小的栈空间。
运行结果
评论