lintcode 前序序列和中序序列构建二叉树

本文主要是介绍lintcode 前序序列和中序序列构建二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

根据前序遍历和中序遍历树构造二叉树.
给出中序遍历：[1,2,3]和前序遍历：[2,1,3]. 返回如下的树:
2
/ \
1 3

"""
Definition of TreeNode:
class TreeNode:def __init__(self, val):self.val = valself.left, self.right = None, None
"""class Solution:"""@param preorder : A list of integers that preorder traversal of a tree@param inorder : A list of integers that inorder traversal of a tree@return : Root of a tree"""def buildTree(self, preorder, inorder):# write your code hereif not preorder or not inorder:return Noneif len(preorder) != len(inorder):return Nonelength = len(inorder)#print "inorder length=",lengthrootkey = 0for i in range(0,length):#print "i = ",iif inorder[i] == preorder[0]:rootkey = i#print "inorder[i]=",inorder[i],"rootkey =",rootkey,ibreakif rootkey == length-1 and inorder[rootkey] != preorder[0]:return None#print "root =", inorder[rootkey]root = TreeNode(inorder[rootkey])#print preorder[1:rootkey],inorder[0:rootkey-1],'nnn',preorder[rootkey+1:],inorder[rootkey+1:]root.left = self.buildTree(preorder[1:rootkey+1],inorder[0:rootkey])root.right = self.buildTree(preorder[rootkey+1:],inorder[rootkey+1:])return root

这里面之前犯了两个错误：
1. list为空和list = None是两个不同的概念，list为空 [], 而list=None， 则是这个对象是None，先在对于None理解还不是很清楚，但是确信不是[], 刚开始判断语句写为 if preorder == None or inorder == None ,结果出现了栈溢出，改为if not preorder or not inorder 之后就好了。有具体明白的同学欢迎在评论下指出原因。像houmou同学说的一样，当序列为[]的时候程序并不会拦截它而是继续通过了，因此会无限调用buildTree（[],[]）.
2. list的切片操作不熟，list = [1,2,3,4], 下标从0开始，list[1:2]是第一个元素，也就是list[1] = 2. 同理，list[1:3] 是指第 1，2个元素下标从0开始）。

这篇关于lintcode 前序序列和中序序列构建二叉树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---