使用 Python 從前序和中序遍歷構建二叉樹

假設我們有兩棵二叉樹的前序和中序遍歷順序。我們需要使用這些順序來生成樹。那麼，如果前序和中序序列為 [3,9,20,15,7] 和 [9,3,15,20,7]，那麼樹將是 −

讓我們看看步驟 −

• 假設該方法使用前序和中序列表呼叫 buildTree
• root := 前序的第一個節點，從前序中刪除第一個節點
• root_index := root.val 在中序列表中的索引
• left or root := buildTree(前序，中序的 0 到 root_index 的子集)
• right or root := buildTree(前序，中序的 root_index + 1 到結尾的子集)

讓我們看以下實現以更好地理解 −

示例

 動態演示

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

輸入

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

輸出

9, 3, 15, 20, 7,

Arnab Chakraborty

更新日期：2020 年 5 月 4 日

977 瀏覽量

啟動 職業生涯

完成課程獲得證書

立即開始