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

DayNightStudy

共 1381字,需浏览 3分钟

 ·

2021-01-30 23:12

根据一棵树的前序遍历与中序遍历构造二叉树。


注意:

你可以假设树中没有重复的元素。


例如,给出


前序遍历 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 = None
class 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)大小的栈空间。


运行结果








浏览 12
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报