Giả sử chúng ta có trình tự duyệt theo thứ tự và sắp xếp trước 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 các trình tự đặt hàng trước và sắp xếp thứ tự là [3,9,20,15,7] 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 đầu tiên từ đơn đặt hàng trước và xóa nút đầu tiên khỏi đơn đặt hàng trước
- root_index:=chỉ mục của root.val từ danh sách inorder
- left hoặc root:=buildTree (đặt hàng trước, tập hợp con của inorder từ 0 đến root_index)
- right hoặc root:=buildTree (đặt hàng trước, tập hợp con của inorder từ root_index + 1 đến cuối)
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([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,