題目：輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果载庭，請重建出該二叉樹。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復的數(shù)字豁遭。例如輸入前序遍歷序列 {1,2,4,7,3,5,6,8} 和中序遍歷序列 {4,7,2,1,5,3,8,6}叭喜，則重建二叉樹并返回。
思路：對于這個題堤框，必須先知道二叉樹的前序遍歷和中序遍歷的特性域滥。前序遍歷是“根左右”，中序遍歷是“左根右”蜈抓，因此可以通過根的位置來劃分左右兩邊的結(jié)點。此外昂儒，在劃分兩邊之后沟使，對于每一邊，采取的策略依然和之前一樣渊跋，因此我們可以考慮采用遞歸來進行操作腊嗡。對于邊界值，當前序或者中序的長度為0時return None拾酝。
Python代碼如下：
class TreeNode(object):
def __init__(self,val):
self.val = val
self.left = None
self.right = None
class Solution(object):
def reConstructBinaryTree(self, pre, tin):
if not pre and not tin:
return None
root = TreeNode(pre[0])
i = tin.index(pre[0])
root.left = self.reConstructBinaryTree(pre[1:i+1],tin[:i])
root.right = self.reConstructBinaryTree(pre[i+1:], tin[i+1:])
return root
s = Solution()
pre = [1, 2, 3, 5, 6, 4]
tin = [5, 3, 6, 2, 4, 1]
res = s.reConstructBinaryTree(pre, tin)
print res.val
print res.left.val
確定left燕少，right 中pre，tin的方法如下圖所示蒿囤，可以根據(jù)圖形實例來進行理解
重建二叉樹.jpg
