举一反三
重建二叉树
http://www.nowcoder.com/questionTerminal/8a19cbe657394eeaac2f6ea9b0f6fcf6
前序+中序
class Solution:
# 返回构造的TreeNode根节点
def reConstructBinaryTree(self, pre, tin):
# write code here
if len(pre)>0:
root = TreeNode(pre[0])
root_idx = tin.index(pre[0])
root.left = self.reConstructBinaryTree(pre[1:1+root_idx],
tin[:root_idx])
root.right = self.reConstructBinaryTree(pre[1+root_idx:],
tin[root_idx+1:])
return root后序+中序
class Solution1:
# 返回构造的TreeNode根节点
def reConstructBinaryTree(self, post, tin):
# write code here
if len(post)>0:
root = TreeNode(post[-1])#后序遍历的倒数第一个节点是根节点
root_idx = tin.index(post[-1])
root.left = self.reConstructBinaryTree(post[:root_idx],tin[:root_idx])
root.right = self.reConstructBinaryTree(post[root_idx:-1],tin[root_idx+1:])
return root层序+中序
class Solution:
def buildtree(self,level,mid):
if len(level)>0:
root=TreeNode(level[0])#根节点
rootid=mid.index(level[0])
midleft=mid[:rootid]#左子树包含的节点
midright=mid[rootid+1:]#右子树包含的节点
levelleft,levelright=[],[]
for node in level:
if node in midleft:
levelleft.append(node)
if node in midright:
levelright.append(node)
root.left=self.buildtree(levelleft,midleft)
root.right=self.buildtree(levelright,midright)
return root
