Xây dựng cây nhị phân từ duyệt Inorder và Postorder trong Python

Giả sử ta có trình tự duyệt inorder và postorder của một cây nhị phân. Ta phải sinh ra cây từ các trình tự này. Ví dụ, nếu postorder và inorder là [9,15,7,20,3] và [9,3,15,20,7], cây sẽ là:

Các bước:

• Giả sử phương thức tên buildTree với danh sách preorder và inorder.

• root := nút cuối từ postorder, và xóa nút đầu tiên từ postorder.

• root_index := chỉ số của root.val từ danh sách inorder.

• left của root := buildTree(tập con inorder từ root_index+1 đến cuối, postorder).

• right của root := buildTree(tập con inorder từ 0 đến root_index, postorder).

Ví dụ

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

def in_cay(root):
    # In theo inorder
    if root is not None:
        in_cay(root.left)
        print(root.data, end=', ')
        in_cay(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()
in_cay(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, 15, 7, 20, 3,