Xây dựng cây BST từ duyệt hậu thứ tự trong Python

Cho chuỗi duyệt hậu thứ tự của BST, xây dựng lại cây. Với BST, inorder là mảng đã sắp xếp.

Ví dụ: postorder [3,9,20,15,7] → inorder [3,7,9,15,20] → cây BST.

Thuật toán

• Inorder = sorted(postorder)
• Áp dụng thuật toán xây dựng cây từ inorder + postorder (giống bài 1003104712)

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()
postorder = [3,9,20,15,7]
inorder = list(sorted([3,9,20,15,7]))
print_tree(ob1.buildTree(inorder, postorder))

Đầu vào

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

Đầu ra

[3,7,9,15,20]