问题描述

输入一棵二叉树前序遍历和中序遍历的结果,请重建该二叉树。

注意:

  • 二叉树中每个节点的值都互不相同;
  • 输入的前序遍历和中序遍历一定合法;

样例

1
2
3
4
5
6
7
8
9
10
11
给定:
前序遍历是:[3, 9, 20, 15, 7]
中序遍历是:[9, 3, 15, 20, 7]

返回:[3, 9, 20, null, null, 15, 7, null, null, null, null]
返回的二叉树如下所示:
3
/ \
9 20
/ \
15 7

解决方案

思路:前序的第一个元素是根结点的值,在中序中找到该值,中序中该值的左边的元素是根结点的左子树,右边是右子树,然后递归的处理左边和右边

不太理解的话需要配合示意图来看:

https://leetcode-cn.com/explore/learn/card/data-structure-binary-tree/2/traverse-a-tree/7/

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
def buildTree(self, preorder, inorder):
if not preorder or not inorder:
return None

index = inorder.index(preorder[0]) # 找到前序遍历结果中第一位对应在中序遍历结果中的位置
left = inorder[0:index]
right = inorder[index+1:]
root = TreeNode(preorder[0])
root.left = self.buildTree(preorder[1:1+len(left)], left)
root.right = self.buildTree(preorder[-len(right):], right)
return root