LeetCode 1008: Xây dựng cây tìm kiếm nhị phân từ thứ tự tiền tố - game 123win

Ngày 17 tháng 11 năm 2019 - Lĩnh vực: Máy tính

1. Mô tả bài toán

Xây dựng một cây tìm kiếm nhị phân (BST) từ danh sách các giá trị được duyệt theo thứ tự tiền tố các game quay hũ uy tín và trả về nút gốc của cây đó.

Cây tìm kiếm nhị phân là loại cây nhị phân thỏa mãn các điều kiện sau:

Với mỗi nút, tất cả các giá trị trong cây con trái (node.left) đều nhỏ hơn giá trị của nút hiện tại (node.val).
Tất cả các giá trị trong cây con phải (node.right) đều lớn hơn giá trị của nút hiện tại (node.val).

Thứ tự duyệt tiền tố hoạt động như sau:

Đầu tiên hiển thị giá trị của nút gốc.
Sau đó duyệt qua cây con trái.
Cuối cùng duyệt qua cây con phải.

Lưu ý: a) Độ dài của danh sách tiền tố nằm trong khoảng: 1 <= preorder.length <= 100; b) Tất cả các giá trị trong danh sách tiền tố đều khác nhau.

Ví dụ minh họa:

Đầu vào: [8,5,1,7,10,12]
Đầu ra: [8,5,10,1,7,null,12]

Biểu diễn game 123win cây:

Nguồn bài toán: LeetCode

2. Ý tưởng giải quyết

Chúng ta sẽ sử dụng phương pháp đệ quy để xây dựng cây tìm kiếm nhị phân.

a) Lấy phần tử đầu tiên trong danh sách duyệt tiền tố làm giá trị của nút gốc.

b) Bắt đầu từ phần tử thứ hai, duyệt qua danh sách từ trái sang phải để tìm điểm chia giữa cây con trái và cây con phải. Điểm này là vị trí xuất hiện lần đầu tiên của một giá trị lớn hơn giá trị của nút gốc.

Các phần tử từ vị trí thứ hai đến trước điểm chia sẽ tạo thành danh sách duyệt tiền tố cho cây con trái.
Các phần tử từ điểm chia đến cuối danh sách sẽ tạo thành danh sách duyệt tiền tố cho cây con phải.

c) Gọi lại hàm xây dựng theo cách đệ quy cho cả cây con trái và cây con phải cho đến khi hoàn thành việc xây dựng toàn bộ cây. Cuối cùng, trả về cây đã được xây dựng.

3. Mã nguồn thực hiện bằng Go

func bstFromPreorder(preorder []int) *TreeNode {
	if len(preorder) == 0 {
		return nil
	}
	val := preorder[0] // Giá trị của nút gốc
	preorder = preorder[1:] // Danh sách còn lại sau khi lấy nút gốc
	i := 0
	for i < len(preorder) && preorder[i] < val {
		i++ // Tìm điểm chia giữa cây con trái và cây con phải
	}
	return &TreeNode{
		val,
		bstFromPreorder(preorder[:i]), // Xây dựng cây con trái
		bstFromPreorder(preorder[i:]), // Xây dựng cây con phải
	}
}

Từ khóa liên quan: #Golang #ThuậtToán

LeetCode 1008&#58; Xây dựng cây tìm kiếm nhị phân từ thứ tự tiền tố - game 123win

LeetCode 1008: Xây dựng cây tìm kiếm nhị phân từ thứ tự tiền tố - game 123win