Kotlin Binary Tree Preorder Traversal (Một giải pháp đệ quy và không sử dụng đệ quy)

Bài đăng này nói về duyệt theo thứ tự trước của cây nhị phân, một phương pháp duyệt qua cây trong đó nút hiện tại được truy cập trước các nút con của nó. Thuật toán duyệt theo thứ tự trước thăm nút gốc trước, sau đó truy cập đệ quy vào cây con bên trái, tiếp theo là cây con bên phải. Kết quả của quá trình truyền tải đặt hàng trước là một danh sách các giá trị của nút theo thứ tự chúng được truy cập. Bài đăng này sẽ giúp bạn hiểu cách duyệt cây nhị phân và cách thực hiện nó theo những cách khác nhau.

Duyệt theo thứ tự trước là một phương pháp duyệt cây nhị phân trong đó nút hiện tại được truy cập trước các nút con của nó. Thuật toán truy cập nút gốc trước, sau đó truy cập đệ quy cây con bên trái, tiếp theo là cây con bên phải. Kết quả của quá trình truyền tải đặt hàng trước là một danh sách các giá trị của nút theo thứ tự chúng được truy cập.

Trong vấn đề này, bạn được cung cấp gốc của một cây nhị phân được đại diện bởi lớp TreeNode trong Kotlin, có thuộc tính val cho giá trị của nút và các thuộc tính left và right tương ứng cho các phần tử con bên trái và bên phải của nó. Nhiệm vụ của bạn là viết hai triển khai của một hàm thực hiện duyệt theo thứ tự trước của cây nhị phân và trả về một danh sách các giá trị của các nút. Một phải là giải pháp đệ quy và giải pháp kia không nên sử dụng đệ quy.

Đây là chữ ký lớp của hàm:

 fun preorderTraversal(root: TreeNode?): List<Int>

Đầu vào của hàm là nút gốc của cây nhị phân và đầu ra là danh sách các số nguyên biểu thị giá trị của các nút theo thứ tự chúng được truy cập trong quá trình truyền tải đơn đặt hàng trước.

Mô tả:

Với gốc của cây nhị phân, hãy trả về giao dịch duyệt theo thứ tự trước của các giá trị nút của nó. Làm điều này với cả giải pháp đệ quy và không sử dụng đệ quy.

 class TreeNode(var `val`: Int) { var left: TreeNode? = null var right: TreeNode? = null }

Đây là một giải pháp đệ quy cho vấn đề:

 fun preorderTraversal(root: TreeNode?): List<Int> { val result = mutableListOf<Int>() if (root == null) return result result.add(root.val) result.addAll(preorderTraversal(root.left)) result.addAll(preorderTraversal(root.right)) return result }

Hàm này thực hiện duyệt theo thứ tự trước của cây nhị phân và trả về danh sách các giá trị của các nút theo thứ tự mà chúng được truy cập.

Các thuật toán hoạt động như sau:

1. Nếu nút gốc là null, trả về một danh sách trống.
2. Thêm giá trị của nút gốc vào danh sách kết quả.
3. Duyệt đệ quy cây con bên trái bằng cách gọi hàm trên cây con bên trái của gốc và thêm danh sách trả về vào danh sách kết quả.
4. Duyệt đệ quy cây con bên phải bằng cách gọi hàm trên cây con bên phải của gốc và thêm danh sách trả về vào danh sách kết quả.
5. Trả về danh sách kết quả.

Thuật toán này có độ phức tạp thời gian là O(n), trong đó n là số nút trong cây và độ phức tạp không gian là O(h), trong đó h là chiều cao của cây (do ngăn xếp cuộc gọi).

Đây là một giải pháp sử dụng phương pháp lặp (nghĩa là không sử dụng đệ quy):

 fun preorderTraversal(root: TreeNode?): List<Int> { val result = mutableListOf<Int>() val stack = Stack<TreeNode>() var current = root while (current != null || stack.isNotEmpty()) { while (current != null) { result.add(current.val) stack.push(current) current = current.left } current = stack.pop() current = current.right } return result }

Hàm này thực hiện duyệt theo thứ tự trước của cây nhị phân và trả về danh sách các giá trị của các nút theo thứ tự mà chúng được truy cập. Nó sử dụng một ngăn xếp để theo dõi các nút vẫn cần được truy cập.

Các thuật toán hoạt động như sau:

1. Khởi tạo một ngăn xếp trống và đặt nút hiện tại vào gốc của cây.

2. Trong khi nút hiện tại không rỗng hoặc ngăn xếp không trống:

   1. Trong khi nút hiện tại không phải là null:

      1. Thêm giá trị của nút hiện tại vào danh sách kết quả.
      2. Đẩy nút hiện tại vào ngăn xếp.
      3. Đặt nút hiện tại thành con trái của nó.

   2. Lấy nút trên cùng ra khỏi ngăn xếp và đặt nút hiện tại thành nút con bên phải của nó.

3. Trả về danh sách kết quả.

Thuật toán này có độ phức tạp thời gian là O(n), trong đó n là số nút trong cây và độ phức tạp không gian là O(h), trong đó h là chiều cao của cây.

Tôi hi vọng cái này giúp được! Hãy cho tôi biết nếu bạn có bất kì câu hỏi nào khác.