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

Giả sử ta có trình tự duyệt inorder và preorder 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 preorder và inorder là [3,9,20,15,7] 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 đầu tiên từ preorder, và xóa nút đầu tiên từ preorder.

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

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

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

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([3,9,20,15,7], [9,3,15,20,7]))

Đầu vào

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

Đầu ra

9, 3, 15, 20, 7,