前言

此題是關于樹的面試題目的常見題型，題目的含義很清晰，這個就不用多說了

解法

關于這道題的解法有很多不同的樣式，通用的解法是這樣的：
假如現(xiàn)在我們有如下兩個遍歷的情況

preorder: [1, 2, 4, 5, 3, 6]
inorder: [4, 2, 5, 1, 6, 3]

那么我們建樹的辦法通常是

1.用先序遍歷的第一個元素也就是1，作為root
2.然后在inorder中查找1的位置
3.然后將inorder以1分割成兩半，一半表示左子樹，一半表示右子樹，這里就是[4, 2, 5]和[6, 3]
4.然后使用[2, 4, 5]和[4, 2, 5]去構(gòu)建左子樹，[3, 6]和[6, 3]去構(gòu)建右子樹

我們以此可以寫出如下的解決辦法：

# 樹的定義
class TreeNode:def __init__(self, x):self.val = xself.left = Noneself.right = None

def buildTree(self, preorder, inorder):if inorder:ind = inorder.index(preorder.pop(0))root = TreeNode(inorder[ind])root.left = self.buildTree(preorder, inorder[0:ind])root.right = self.buildTree(preorder, inorder[ind+1:])return root

如果我們考慮到不停的pop(0),這樣效率不是很高的話，我們可稍微優(yōu)化一下：

    def buildTree(self, preorder, inorder):""":type preorder: List[int]:type inorder: List[int]:rtype: TreeNode"""def build(preorder, inorder):if inorder:ind = inorder.index(preorder.pop())root = TreeNode(inorder[ind])root.left = build(preorder, inorder[ind+1:])root.right = build(preorder, inorder[:ind])return rootpreorder.reverse()inorder.reverse()return build(preorder, inorder)

這里我們先將列表翻轉(zhuǎn)了，這樣，我們彈棧的時候，就不會造成很多的列表元素的移動。
但是即使如此，我們考慮最壞的情況：這個樹不是平衡的而是一顆只有左子樹的斜樹，那么，他的先序遍歷和中序遍歷是完全相反的，整個算法過程中進行第二步的查找過程時候所花費的時間為O(n^2),由于我們使用的遞歸的實現(xiàn)方法，所以空間復雜度也是O(n^2)

優(yōu)化時間復雜度

我們可以省略在Inorder中查找這一步，不是找到1在inorder中的index，把數(shù)組分成幾個部分，然后遞歸它們上，而是遞歸到全部剩下的數(shù)組，當你遇到1的時候就停止，具體的實現(xiàn)如下：

def buildTree(self, preorder, inorder):def build(stop):if inorder and inorder[-1] != stop:root = TreeNode(preorder.pop())root.left = build(root.val)inorder.pop()root.right = build(stop)return rootpreorder.reverse()inorder.reverse()return build(None)

其中當我們遇到了在inorder中遇到了stop時候，證明我們在這里樹要開始“轉(zhuǎn)向”了，即從左子樹變成右子樹了，所以我們繼續(xù)接著上一次的stop來走

再優(yōu)化空間復雜度

    def buildTree2(self, preorder, inorder):if len(preorder) == 0:return Nonei, j = 1, 0root = TreeNode(preorder[0])stack = [root]while i < len(preorder):node = TreeNode(preorder[i])tmp = Nonewhile stack and stack[-1].val == inorder[j]:tmp = stack.pop()j += 1if tmp:tmp.right = nodeelse:stack[-1].left = nodestack.append(node)i += 1return root

我們現(xiàn)在不使用遞歸了，而是直接使用棧來解決這個問題，我們從頭到尾過一遍preorder，把過的元素存在棧中，如果發(fā)現(xiàn)preorder中有元素在inorder中出現(xiàn)了，就開始把棧中元素彈出來，之所以這樣做，是因為好比已經(jīng)建完了半邊的樹，現(xiàn)在要換半邊繼續(xù)建樹了

參考

leetcode solution 1
leetcode solution 2

總結(jié)

以上是生活随笔為你收集整理的python实现二叉树的重建1 之由前序遍历和中序遍历重建的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。