Giả sử chúng ta có gốc của một cây nhị phân, mỗi nút trong cây có một giá trị duy nhất. Sau khi loại bỏ tất cả các nút có giá trị trong to_delete, chúng ta chỉ còn lại một khu rừng. Chúng ta phải tìm rễ cây trong khu rừng còn lại. Vì vậy, nếu đầu vào giống như
nếu mảng to_delete giống như [3,5], thì đầu ra sẽ là
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- Xác định res một mảng
- Xác định phương thức giải quyết (), phương thức này sẽ lấy nút, mảng to_delete và thông tin kiểu Boolean cho biết rằng nút có phải là gốc hay không. Phương thức sẽ hoạt động như dưới đây−
- nếu nút là null, thì trả về null
- flag:=true nếu giá trị của nút nằm trong mảng to_delete
- nếu cờ là false và is_root là true, thì hãy chèn nút vào res
- left of node:=giải quyết (left of node, to_delete, flag)
- bên phải của nút:=giải quyết (bên phải của nút, để xóa, cờ)
- không trả về giá trị nào khi cờ được đặt, ngược lại là false
- Gọi phương thức giải quyết () từ phương thức chính như giải quyết (node, to_delete, true)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
class Giải pháp (đối tượng):def delNodes (self, root, to_delete):"" ":type root:TreeNode:type to_delete:List [int]:rtype:List [TreeNode]" "" to_delete =set (to_delete ) self.res =[] self.solve (root, to_delete, True) trả về self.res def giải quyết (self, node, to_delete, is_root):if not node:return None flag =node.val in to_delete if not flag and is_root:self.res.append (node) node.left =self.solve (node.left, to_delete, flag) node.right =self.solve (node.right, to_delete, flag) trả về Không nếu cờ khác nútĐầu vào
[1,2,3,4,5,6,7] [3,5]Đầu ra
[[1,2, null, 4], [6], [7]]