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

Cho mảng duyệt hậu thứ tự (postorder) của cây tìm kiếm nhị phân (BST), xây dựng lại cây BST.

Ví dụ: [6, 12, 10, 55, 45, 15] → cây BST tương ứng.

Thuật toán dùng Stack

• Nút gốc = phần tử cuối postorder
• Đẩy gốc vào stack
• Duyệt ngược postorder (từ n-2 về 0):
  • Tạo nút x từ postorder[i]
  • Khi stack không rỗng và postorder[i] < stack[-1].val: pop stack lưu vào temp
  • Nếu temp tồn tại: temp.left = x, ngược lại: stack[-1].right = x
  • Đẩy x vào stack
• Trả về gốc

Ví dụ mã Python

class TreeNode:
    def __init__(self, data=0):
        self.val = data
        self.left = None
        self.right = None

def solve(postorder):
    n = len(postorder)
    root = TreeNode(postorder[n-1])
    stk = [root]
    i = n - 2
    while i >= 0:
        x = TreeNode(postorder[i])
        temp = None
        while stk and postorder[i] < stk[-1].val:
            temp = stk.pop()
        if temp:
            temp.left = x
        else:
            stk[-1].right = x
        stk.append(x)
        i -= 1
    return root

def build_tree(postorder):
    return solve(postorder)

def inord(node):
    if node:
        inord(node.left)
        print(node.val, end=" ")
        inord(node.right)

postorder = [6, 12, 10, 55, 45, 15]
root = build_tree(postorder)
print("Inorder traversal:", end=" ")
inord(root)

Đầu vào

[6, 12, 10, 55, 45, 15]

Đầu ra

6 10 12 15 45 55