在 Python 中從後序遍歷和中序遍歷構建二叉樹

假設我們有二叉樹的中序遍歷和後序遍歷序列。我們需要從這些序列中生成一棵樹。因此，如果後序遍歷和中序遍歷序列是 [9,15,7,20,3] 和 [9,3,15,20,7]，則這棵樹將為：

讓我們看看步驟：

  • 定義一個方法 build_tree()，它將使用中序、後序：

  • 如果中序列表不為空：

    • root := 建立一個樹節點，其值為後序的最後一個值，然後刪除該元素

    • ind := 在中序列表中找到 root 資料的索引

    • root 的右節點 := build_tree(從索引 ind 到末尾的中序、後序)

    • root 的左節點 := build_tree(從 0 到索引 ind - 1 的中序、後序)

  • return root

示例

讓我們看看以下實現，以便更好地理解：

 演示

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right
def print_tree(root):
   if root is not None:
      print_tree(root.left)
      print(root.data, end = ', ')
      print_tree(root.right)
class Solution(object):
   def buildTree(self, inorder, postorder):
      if inorder:
         root = TreeNode(postorder.pop())
         ind = inorder.index(root.data)
         root.right = self.buildTree(inorder[ind+1:],postorder)
         root.left = self.buildTree(inorder[:ind],postorder)
         return root
ob1 = Solution()
print_tree(ob1.buildTree([9,3,15,20,7], [9,15,7,20,3]))

輸入

[9,3,15,20,7]
[9,15,7,20,3]

輸出

[9,3,15,20,7]

更新於：2020 年 8 月 27 日

539 次瀏覽

開啟你的 職業生涯

完成課程即可獲得認證

開始學習
廣告