重建二叉树

题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{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 root

1、为什么倒数第二行是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, 空列表[], 空字典{}, 空元组()时对你的判断没有影响才行。

另一个python解法

class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        # write code here
        if len(pre) == 0:
            return None
        elif len(pre) == 1:
            return TreeNode(pre[0])
        else:
            ans = TreeNode(pre[0])
            ans.left = self.reConstructBinaryTree(pre[1:tin.index(pre[0])+1],   tin[:tin.index(pre[0])])
            ans.right = self.reConstructBinaryTree(pre[tin.index(pre[0])+1:], tin[tin.index(pre[0])+1:])
            return ans