Xây dựng cây nhị phân từ duyệt hậu thứ tự và trung thứ tự trong Python

Cho chuỗi duyệt trung thứ tự (inorder) và hậu thứ tự (postorder) của cây nhị phân, xây dựng lại cây.

Ví dụ: inorder [9,3,15,20,7], postorder [9,15,7,20,3] → cây tương ứng.

Thuật toán đệ quy

• Nếu inorder không rỗng:
  • Gốc = phần tử cuối postorder (pop)
  • Tìm chỉ số ind của gốc trong inorder
  • Cây con phải = build_tree(inorder[ind+1:], postorder)
  • Cây con trái = build_tree(inorder[:ind], postorder)
• Trả về gốc

Ví dụ mã Python

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]))

Đầu vào

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

Đầu ra

[9,3,15,20,7]