题目描述

[EN | CN]

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

注意:

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

例如,给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树:

3
   / \
  9  20
    /  \
   15   7

解法 1:递归

题目的意思是要根据 前序遍历中序遍历 的顺序,来推导出整棵树。我们首先要明白这两种遍历方式的定义与特点:

  • 前序遍历的顺序是 -> -> ,第一个结点一定是根;
  • 中序遍历的顺序是 -> -> ,根将左右字数切割开来。

根据以上特点,其实我们根据前序遍历和中序遍历的顺序可以很容易地推出整棵树。以题目给出的例子为例,步骤如下:

  1. 根据前序遍历的顺序 [3, 9, 20, 15, 7],我们知道了整棵树的根结点是 3
  2. 再根据中序遍历的顺序 [9, 3, 15, 20, 7],我们以根结点 3 将其拆成两部分,分别为左子树的中序遍历 [9]、右子树的中序遍历 [15, 20, 7]
  3. 根据切开的两棵子树,再回到前序遍历,我们又可以得到左子树的前序遍历 [9]、右子树的前序遍历 [20, 15, 7]
  4. 对每棵子树递归重复以上 3 步,直到不可切为止。

假设结点数量为 $n$,那么

  • 时间复杂度为 $O(n)$;
  • 空间复杂度为 $O(n)$。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
# 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:
        if len(preorder) == 0:
            return None

        root_node = TreeNode(preorder[0])
        l_len = inorder.index(preorder[0])

        root_node.left = self.buildTree(preorder[1:l_len + 1], inorder[:l_len])
        root_node.right = self.buildTree(preorder[l_len + 1:], inorder[l_len + 1:])

        return root_node
  • 执行用时:196 ms,在所有 Python3 提交中击败了 61.27% 的用户。
  • 内存消耗:87.6 MB,在所有 Python3 提交中击败了 7.60% 的用户。