# 【LeetCode 二叉树专项】从前序与中序遍历序列构造二叉树（105）

## 1. 题目

### 1.1 示例

• 示例

1

1

1

• 输入： preorder = [3, 9, 20, 15, 7]inorder = [9, 3, 15, 20, 7]
• 输出： [3, 9, 20, null, null, 15, 7]
• 示例

2

2

2

• 输入： preorder = [-1]inorder = [-1]
• 输出： [-1]

### 1.3 限制

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

## 2. 解法一（递归）

### 2.1 分析

def _maximum_binary_tree(self, nums: List[int], start: int, stop: int) -> Optional[TreeNode]:


def _build_tree(self, preorder: List[int], inorder: List[int],
pre_start: int, pre_stop, in_start: int, in_stop: int) -> Optional[TreeNode]:


• 首先，在通过 preorder 确定根节点的 val 域之后，可以找到其对应在 inorder 中的位置；
• 接着，根据中序遍历性质可知根节点左边的元素都是其左子树节点的 val 值，右边元素都是其右子树节点的 val 值。

### 2.2 实现

from collections import deque
from typing import List, Optional

class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right

class Solution:
def _build_tree(self, preorder: List[int], inorder: List[int],
pre_start: int, pre_stop, in_start: int, in_stop: int) -> Optional[TreeNode]:
if pre_start > pre_stop or in_start > in_stop:
return
index = inorder.index(preorder[pre_start], in_start, in_stop + 1)
root = TreeNode(preorder[pre_start])
root.left = self._build_tree(preorder, inorder,
pre_start + 1, pre_start + index - in_start,
in_start, index - 1)
root.right = self._build_tree(preorder, inorder,
pre_start + index - in_start + 1, pre_stop,
index + 1, in_stop)
return root

def build_tree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
return self._build_tree(preorder, inorder, 0, len(preorder) - 1, 0, len(inorder) - 1)

def main():
preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]
sln = Solution()
root = sln.build_tree(preorder, inorder)

tree = []
visiting = deque([root])
while visiting:
node = visiting.popleft()
if node:
tree.append(node.val)
visiting.append(node.left)
visiting.append(node.right)
else:
tree.append(None)

while True:
if not tree[-1]:
tree.pop()
else:
break

print(tree)  # [3, 9, 20, None, None, 15, 7]

if __name__ == '__main__':
main()



### 2.3 复杂度

• 时间复杂度：

O

(

n

)

O(n)

，其中

n

n

是树中的节点个数。

• 空间复杂度：

O

(

n

)

O(n)

，除去返回的答案需要的

O

(

n

)

O(n)

空间之外，我们还需要使用

O

(

n

)

O(n)

的空间存储哈希映射，以及

O

(

h

)

O(h)

（其中

h

h

是树的高度）的空间表示递归时栈空间。这里

h

<

n

h<n

，所以总空间复杂度为

O

(

n

)

O(n)

THE END

)">