Giả sử chúng ta có trình tự duyệt thứ tự thứ tự và thứ tự sau của một cây nhị phân. Chúng ta phải tạo cây từ các chuỗi này. Vì vậy, nếu trình tự postorder và inorder là [9,15,7,20,3] và [9,3,15,20,7], thì cây sẽ là -
Hãy để chúng tôi xem các bước -
- Giả sử phương thức được gọi là buildTree với danh sách đặt hàng trước và đặt hàng trước
- root:=nút cuối cùng từ đơn hàng đăng và xóa nút đầu tiên khỏi đơn hàng đăng
- root_index:=chỉ mục của root.val từ danh sách inorder
- left hoặc root:=buildTree (tập hợp con của inorder từ root_index + 1 đến end, postorder)
- right hoặc root:=buildTree (tập hợp con của inorder từ chỉ mục 0 đến root_index, postorder)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
class TreeNode: def __init__(self, data, left = None, right = None): self.data = data self.left = left self.right = right def print_tree(root): #print using inorder traversal if root is not None: print_tree(root.left) print(root.data, end = ', ') print_tree(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() 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, 15, 7, 20, 3,