recursive solution.
the last element in the postorder array is always the root
pass index instead of array to save memory
# 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 buildTree(i_start,i_end,p_start,p_end):
if i_start==i_end:return None
#print 'create root',postorder[p_end-1]
root=TreeNode(postorder[p_end-1])
root_idx=inorder[i_start:i_end].index(root.val)
#print 'create left root'
root.left=buildTree(i_start,i_start+root_idx,p_start,p_start+root_idx)
#print 'create right root'
root.right=buildTree(i_start+root_idx+1,i_end,p_start+root_idx,p_end-1)
return root
if not inorder or not postorder:
return None
return buildTree(0,len(inorder),0,len(postorder))
106. Construct Binary Tree from Inorder and Postorder Traversal
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- Given inorder and postorder traversal of a tree, construc...
- Given inorder and postorder traversal of a tree, construc...
- Given inorder and postorder traversal of a tree, construc...
- 原题 中序遍历和后序遍历树构造二叉树 给出树的中序遍历： [1,2,3] 和后序遍历： [1,3,2]返回如下的树...
- 由西南财经大学学生职业规划与就业指导中心《职场起跑线》出品，旨在提供就业与职业规划方面的指导，助全国广大学生群体迅...
