Ngày 06 tháng 10 năm 2020 Lĩnh vực Máy tính
1 Mô tả bài toán
Cho trước hai danh sách: một là kết quả duyệt cây theo thứ tự tiền tố (preorder) và một là kết quả duyệt cây theo thứ tự trung tố (inorder). Yêu cầu là tái tạo lại cây nhị phân ban đầu từ hai danh sách này. Lưu ý:
- Giả sử rằng tất cả các nút trong cây đều có giá trị khác nhau.
Ví dụ minh họa:
- Đầu vào
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
3
/ \
9 20
/ \
15 7
Nguồn gốc bài toán: LeetCode
2 Ý tưởng giải quyết
Trong bài viết này, chúng ta sẽ áp dụng phương pháp đệ quy để giải quyết vấn đề:
- Từ danh sách duyệt theo tiền tố, phần tử đầu tiên luôn là giá trị của nút gốc;
- Truy xuất qua danh sách duyệt theo trung tố từ trái sang phải, tìm vị trí mà giá trị của nút gốc xuất hiện. Phần bên trái của vị trí này sẽ là cây con trái của nút gốc, phần bên phải sẽ là cây con phải của nó;
- Quay trở lại danh sách duyệt theo tiền tố, bỏ qua phần tử đầu tiên, tiếp tục lấy số lượng phần tử tương ứng với cây con trái đã xác định ở bước trên, phần còn lại sẽ là cây con phải;
- Thực hiện lặp lại quá trình này theo cách đệ quy cho đến khi cả hai danh sách duyệt theo tiền tố và trung tố đều trống.
i99bet 3 Mã nguồn Golang
func buildTree(preorder []int, inorder []int) *TreeNode {
if len(preorder) == 0 {
return nil
}
root := preorder[0]
i := 0
for ; i < len(inorder); i++ {
if root == inorder[i] {
break
}
}
return &TreeNode{
Val: root,
Left: buildTree(preorder[1:i+1], inorder[:i]),
Right: buildTree(preorder[i+1:], inorder[i+1:]),
}
}
4 Mã nguồn Python
class Solution:
def build_tree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
if len(preorder) == 0:
return None
val = preorder[0]
for i in range(len(inorder)):
if val == inorder[i]:
break
node = TreeNode(val=val)
node.left = self.build_tree(preorder[1:1 + i], inorder[:i])
node.right = self.build_tree(preorder[1 + i:], inorder[i + 1:])
return node
#Golang #Python #Thuật_toán