題目描述
輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請重建出該二叉樹灿渴。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹并返回柜某。
以中序和前后序建成樹的思想已經(jīng)不用再闡述了靠娱，簡歷樹主要靠的是遞歸
代碼展示
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的當(dāng)前值在tin中的位置
root.left = self.reConstructBinaryTree(pre, tin[:index])
#tin[:index]意思是從0開始輸出index個個數(shù)中序的值,左邊的全是跟的左子樹
root.right = self.reConstructBinaryTree(pre, tin[index+1:])
#tin[index + 1:]意思是從第index+2后所有元素,全是跟的右子樹部分
return root
1沧烈、為什么倒數(shù)第二行是tin[index+1:]
答：因為是右子樹部分，若是tin[index:]則包含了root本身
2像云、為什么pre沒有變化锌雀，上下的都是pre
答：因為pop掉了前序的第一個，也就是樹整體的根迅诬，且是處理完了左子樹腋逆，才會處理右子樹，按照前序序列左子樹一個個pop掉侈贷，當(dāng)先處理左子樹的時候pre[:index-1]就是pre惩歉，所以，上面的pre非下面的pre俏蛮。
3撑蚌、為什么是 if not pre or not tin 而不是 if pre == None or tin == None
答：網(wǎng)上有這樣的答案
代碼中經(jīng)常有三中方式判斷變量是否為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, 空列表[], 空字典{}, 空元組()都相當(dāng)于False 搏屑，因此在使用列表的時候争涌，如果你想?yún)^(qū)分x==[]和x==None兩種情況的話, 此時
if not x:將會出現(xiàn)問題：
>>> 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==[]的情況也判斷進(jìn)來了辣恋，此種情況下將無法區(qū)分亮垫。
對于習(xí)慣于使用if not x這種寫法的pythoner，必須清楚x等于None, False, 空字符串"", 0, 空列表[], 空字典{}, 空元組()時對你的判斷沒有影響才行伟骨。
而對于if x is not None和if not x is None寫法饮潦，很明顯前者更清晰，而后者有可能使讀者誤解為if (not x) is None底靠，因此推薦前者害晦，同時這也是谷歌推薦的風(fēng)格結(jié)論：
if x is not None是最好的寫法，清晰暑中，不會出現(xiàn)錯誤壹瘟，以后堅持使用這種寫法。
使用if not x這種寫法的前提是：必須清楚x等于None, False, 空字符串"", 0, 空列表[], 空字典{}, 空元組()時對你的判斷沒有影響才行鳄逾。
另一個python解法
class Solution:
# 返回構(gòu)造的TreeNode根節(jié)點
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
