LEETCODE 106. 从中序与后序遍历序列构造二叉树

LEETCODE 106. 从中序与后序遍历序列构造二叉树

题目描述

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

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

例如,给出

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

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, inorder, postorder):
		"""
		:type inorder: List[int]
		:type postorder: List[int]
		:rtype: TreeNode
		"""
		def recursion(in_order, post_order):
			if(not in_order or not post_order):
				return None
			if(len(in_order)==1 and len(post_order)==1):
				return TreeNode(post_order[0])
			root = TreeNode(post_order[-1])
			index = in_order.index(post_order[-1])
			in_left = in_order[:index]
			in_right = in_order[index+1:]
			index = len(in_left)
			post_left = post_order[:index]
			post_right = post_order[index:-1]
			root.left = recursion(in_left, post_left)
			root.right = recursion(in_right, post_right)
			return root
		return recursion(inorder, postorder)
                                                                           
0 次阅读

发表评论

电子邮件地址不会被公开。