Các nút màu xanh là các nút đang được quan sát.
Với cách đặt camera như hình bên phải, ta chỉ cần 1 camera. Với cách đặt như hình bên trái, ta cần 2 camera. Từ đó, ta thấy nên giải bài toán này với post-order traversal.
Để biết nút có đang được quan sát hay không, ta có thể dùng HashSet, mỗi lần ta đặt camera tại 1 nút ta thêm các nút đang được quan sát vào HashSet. Xem thêm về giải thuật này tại
đây.
Giải thuật có độ phức tạp:
- Time Complexity: là O(n),
- Space Complexity: là O(n) cho
Set<TreeNode> covered
.
Ta có thể tối ưu Space Complexity của giải thuật trên bằng cách định nghĩa một số trạng thái của nút như sau:
- CoverWithCamera: nút đang được quan sát và có camera.
- CoverNoCamera: nút đang được quan sát và không có camera. Hay nút đang được quan sát bởi camera đặt tại nút con.
- NotCover: nút đang không được quan sát.
Như vậy, nếu nút là null
, nút sẽ có trạng thái CoverNoCamera
.
Ta thực hiện post-order travel như giải thuật trên, và kiểm tra trạng thái của các nút con:
- Nếu 1 trong 2 nút con được quan sát, ta cần đặt camera tại nút hiện tại.
- Nếu 2 nút con đều ở trạng thái
CoverNoCamera
, nút hiện tại đang không được quan sát, trạng thái NotCover
.
- Trong những trường hợp còn lại, 1 trong 2 nút con có camera, nút hiện tại ở trạng thái
CoverNoCamera
.
Mời các bạn đọc kỹ hơn về giải thuật này tại link bên dưới.
(by phucnh)