题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
以中序和前后序建成树的思想已经不用再阐述了，遍历树主要靠的是递归
代码展示
class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: def reConstructBinaryTree(self, pre, tin): if not pre or not tin: #判断是否为None return None root = TreeNode(pre.pop(0)) #root为前序的头节点 index = tin.index(root.val) #index为root的当前值在tin中的位置 root.left = self.reConstructBinaryTree(pre, tin[:index]) #tin[:index]意思是从0开始输出index个个数中序的值,左边的全是跟的左子树 root.right = self.reConstructBinaryTree(pre, tin[index+1:]) #tin[index + 1:]意思是从第index+2后所有元素,全是跟的右子树部分 return root1、为什么倒数第二行是tin[index+1:]
答：因为是右子树部分，若是tin[index:]则包含了root本身
2、为什么pre没有变化，上下的都是pre
答：因为pop掉了前序的第一个，也就是树整体的根，且是处理完了左子树，才会处理右子树，按照前序序列左子树一个个pop掉，当先处理左子树的时候pre[:index-1]就是pre，所以，上面的pre非下面的pre。
3、为什么是 if not pre or not tin 而不是 if pre == None or tin == None
答：网上有这样的答案
代码中经常有三种方式判断变量是否为None，主要有三种写法: (1) if x is None: (2) if not x: (3) if not x is None:（这句这样理解更清晰if not (x is None)）
>>> x = 1 >>> not x False >>> x = [1] >>> not x False >>> x = 0 >>> not x True >>> x = [0] # You don't want to fall in this one. >>> not x False在python中 None, False, 空字符串"", 0, 空列表[], 空字典{}, 空元组()都相当于False ，因此在使用列表的时候，如果你想区分x==[]和x==None两种情况的话, 此时if not x:将会出现问题：
>>> x = [] >>> y = None >>> >>> x is None False >>> y is None True >>> >>> >>> not x True >>> not y True >>> >>> >>> not x is None True >>> not y is None False也许你是想判断x是否为None，但是却把x==[]的情况也判断进来了，此种情况下将无法区分。 对于习惯于使用if not x这种写法的pythoner，必须清楚x等于None, False, 空字符串"", 0, 空列表[], 空字典{}, 空元组()时对你的判断没有影响才行。 而对于if x is not None和if not x is None写法，很明显前者更清晰，而后者有可能使读者误解为if (not x) is None，因此推荐前者，同时这也是谷歌推荐的风格
结论：if x is not None是最好的写法，清晰，不会出现错误，以后坚持使用这种写法。使用if not x这种写法的前提是：必须清楚x等于None, False, 空字符串"", 0, 空列表[], 空字典{}, 空元组()时对你的判断没有影响才行。
转载链接：https://www.jianshu.com/p/86dea051d145
