Ngày 21 tháng 11 năm 2019 Rik68 Club Game Bài Tiền Thật - Lĩnh vực Công nghệ thông tin
1. Mô tả bài toán Cho một cây nhị phân, hãy trả về danh sách các giá trị của nó khi duyệt qua từng tầng theo thứ tự hình chữ Z. (Ví dụ: tầng đầu tiên từ trái sang phải, tầng tiếp theo từ phải sang trái và cứ thế luân phiên cho Sam86 Club Choi Game Bài đến khi duyệt xong tất cả các tầng).
Ví dụ: Đầu vào:
[3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
Đầu ra:
[[3], [20,9], [15,7]]
Nguồn gốc bài toán: LeetCode
2. Cách tiếp cận giải quyết Chúng ta sẽ bắt đầu bằng cách đặt nút gốc là tầng số 0. Sử dụng thuật toán lặp lại (iteration), mỗi lần duyệt qua một tầng, ta sẽ kiểm tra xem tầng hiện tại có phải là tầng chẵn hay lẻ. Nếu là tầng chẵn, chúng ta thêm các nút con vào danh sách theo thứ tự bình thường (từ trái sang phải). Ngược lại, nếu là tầng lẻ, chúng ta sẽ thêm các nút con vào danh sách theo thứ tự ngược lại (từ phải sang trái). Sau khi hoàn thành việc duyệt qua tất cả các tầng, kết quả cuối cùng sẽ được trả về.
3. Mã nguồn thực hiện bằng Golang
func zigzagLevelOrder(root *TreeNode) [][]int {
if root == nil {
return [][]int{}
}
var allVals [][]int
nodes := []*TreeNode{root}
level := 0
for len(nodes) > 0 {
var vals []int
tmp := nodes[:]
nodes = []*TreeNode{}
for _, p := range tmp {
if level%2 == 0 {
vals = append(vals, p.Val)
} else {
vals = append([]int{p.Val}, vals...)
}
if p.Left != nil {
nodes = append(nodes, p.Left)
}
if p.Right != nil {
nodes = append(nodes, p.Right)
}
}
allVals = append(allVals, vals)
level++
}
return allVals
}
Mã nguồn trên sử dụng cấu trúc dữ liệu hàng đợi để xử lý từng tầng của cây nhị phân. Mỗi vòng lặp xử lý một tầng riêng biệt và áp dụng quy tắc duyệt theo chiều ngược lại tùy thuộc vào số thứ tự của tầng đó.
Từ khóa: #Golang #ThuậtToán