Skip to content

105. Construct Binary Tree from Preorder and Inorder Traversal 从前序与中序遍历序列构造二叉树

难度: 中等

刷题内容

原题连接

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

内容描述

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

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

例如,给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树:

    3
   / \
  9  20
    /  \
   15   7

解题方案

思路 1

一句话,看到树🌲就要想到递归

  • preorder 是 根 -> 左 -> 右
  • inorder 是 左 -> 根 -> 右

首先pre的第一个就是整个树的root, 假设 preorder[0] = inorder[k],那么inorder的前k-1个就是树的左子树,后面部分就是树的右子树

class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        if not preorder or len(preorder) == 0:
            return None
        root = TreeNode(preorder[0])
        k = inorder.index(preorder[0])
        root.left = self.buildTree(preorder[1:k+1], inorder[0:k])
        root.right = self.buildTree(preorder[k+1:], inorder[k+1:])
        return root


回到顶部