Xây dựng cây nhị phân từ tiền thứ tự và hậu thứ tự - LeetCode 889 - m88vin - cổng game quốc tế

Ngày 17 tháng 11 năm 2019 m88vin - cổng game quốc tế - Lĩnh vực Máy tính

1. Mô tả bài toán Cho trước danh sách các phần tử theo thứ tự tiền thứ tự (preorder) và hậu thứ tự (postorder), hãy trả về bất kỳ cây nhị phân nào thỏa mãn điều kiện.

Lưu ý: a) 1 <= độ dài của pre == độ dài của post <= 30; b) Các mảng pre[] và post[] đều là hoán vị của các số từ 1 đến độ dài của pre; c) Đầu vào đảm bảo luôn có lời giải, trong trường hợp có nhiều lời giải, bạn có thể trả về bất kỳ cây nhị phân nào.

Ví dụ: Đầu vào: j8bet com pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1] Đầu ra: [1,2,3,4,5,6,7]

Nguồn gốc bài toán: LeetCode

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

Chúng ta áp dụng phương pháp đệ quy để giải bài toán này. Phần tử đầu tiên của danh sách tiền thứ tự chính là gốc của cây. Trong khi đó, phần tử cuối cùng của danh sách hậu thứ tự cũng chính là gốc của cây.

Sau khi xác định được gốc, chúng ta loại bỏ phần tử đầu tiên khỏi danh sách tiền thứ tự và phần tử cuối cùng khỏi danh sách hậu thứ tự. Tiếp theo, chúng ta sẽ xây dựng hai nhánh con trái và phải.

Phần tử đầu tiên của danh sách tiền thứ tự sau khi đã cắt đi phần đầu chính là gốc của cây con trái. Từ phần tử này, chúng ta tìm kiếm nó trong danh sách hậu thứ tự (sau khi đã cắt phần cuối). Khi tìm thấy vị trí xuất hiện của nó, chúng ta chia danh sách hậu thứ tự thành hai phần tại vị trí đó. Phần trước và bao gồm phần tử này sẽ là danh sách hậu thứ tự của cây con trái, phần còn lại sẽ là danh sách hậu thứ tự của cây con phải.

Tương tự, chúng ta cũng chia danh sách tiền thứ tự thành hai phần. Số lượng phần tử tương ứng với danh sách hậu thứ tự của cây con trái sẽ được lấy làm danh sách tiền thứ tự của cây con trái, phần còn lại sẽ thuộc về danh sách tiền thứ tự của cây con phải.

Cuối cùng, chúng ta sử dụng phương pháp đệ quy để xây dựng cả hai cây con trái và phải. Khi hoàn thành việc xây dựng các cây con, toàn bộ cây sẽ được hoàn thiện.

3. Mã nguồn Golang

func constructFromPrePost(pre []int, post []int) *TreeNode {
	if len(pre) == 0 {
		return nil
	}
	if len(pre) == 1 {
		return &TreeNode{Val: pre[0]}
	}
	root := &TreeNode{Val: pre[0]}
	pre = pre[1:]
	post = post[:len(post)-1]
	i := 0
	for i < len(post) {
		if pre[0] == post[i] {
			break
		}
		i++
	}
	root.Left = constructFromPrePost(pre[:i+1], post[:i+1])
	root.Right = constructFromPrePost(pre[i+1:], post[i+1:])
	return root
}

Mã nguồn trên minh họa cách xây dựng cây nhị phân từ hai danh sách tiền thứ tự và hậu thứ tự bằng ngôn ngữ lập trình Go. Phương pháp sử dụng kỹ thuật đệ quy giúp đơn giản hóa quá trình xử lý và dễ dàng hiểu hơn.

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