题目描述

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

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

例如，给出

前序遍历 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(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
	def buildTree(self, preorder, inorder):
		"""
		type preorder: List[int]
		:type inorder: List[int]
		:rtype: TreeNode
		"""
		def recursion(pre_order, in_order):
			if(not pre_order or not in_order):
				return None
			if(len(pre_order)==1 and len(in_order)==1):
				return TreeNode(pre_order[0])
			root = TreeNode(pre_order[0])
			index = in_order.index(pre_order[0])
			in_left = in_order[:index]
			in_right = in_order[index+1:]
			
			index = len(in_left)+1
			pre_left = pre_order[1:index]
			pre_right = pre_order[index:]
			root.left = recursion(pre_left, in_left)
			root.right = recursion(pre_right, in_right)
			return root
		return recursion(preorder, inorder)
                                                                           

2 次阅读