Leetcode之旅|還原二叉樹

1. 題目描述

前兩天的文章都是從已有的一棵樹出發，得到各種遍歷的結果，今天我們反其道而行之，從遍歷結果還原二叉樹結構。

2. 思路

2.1. 從前序遍歷和中序遍歷結果還原二叉樹

如下圖一棵二叉樹：

　　其中序遍歷和前序遍歷結果分別如下：

　　那麼我們如果只知道這兩個遍歷結果的List，那我們是否還原出圖1的二叉樹結構呢？答案當然是肯定的，具體思路如下圖3所示。

1. 首先由前序遍歷的第一個節點A確認其為根節點root；

2. 在中序遍歷的結果中找到root，這時候可以知道在中序遍歷結果中，A左邊的節點 DBGE為A的左子樹的節點，而A右邊的節點CF為A的右子樹的節點；

3. 有上一步可以知道A的左右子樹的節點個數，可以在前序遍歷的結果中把左子樹和右子樹的節點分開；

4. 在左右子樹中遞歸第1,2,3步直到節點為空。

代碼如下：

class Solution: def buildTree(self, preorder, inorder): """ :type preorder: List[int] :type inorder: List[int] :rtype: TreeNode """ length = len(preorder) if not length: return None root = TreeNode(preorder[0]) i = inorder.index(preorder[0]) if i: root.left = self.buildTree(preorder[1:1+i],inorder[0:i]) if length-i: root.right=self.buildTree(preorder[i+1:],inorder[i+1:]) return root

2. 2 從中序遍歷和後序遍歷還原二叉樹

從中序遍歷和後序遍歷還原二叉樹的方法是一樣的，不同的是在找根節點的確認方法不同：後序遍歷結果的最後一個節點為根節點。剩下的步驟都是一樣的。

代碼如下：

class Solution: def buildTree(self, inorder, postorder): length = len(inorder) if not length: return None node = postorder[-1] i = inorder.index(node) root = TreeNode(node) if i: root.left=self.buildTree(inorder[0:i],postorder[0:i]) if length-i: root.right=self.buildTree(inorder[i+1:],postorder[i:length-1]) return root

3. 總結

只學到一些微不足道的小知識，還沒到深刻思考的地步，繼續加油吧！

推薦閱讀：