427. Construct Quad Tree
Tags:
Medium
Skills:
Divide & conquer
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Là một DSA dạng cây được sử dụng để phân chia và quản lý không gian hai chiều (2D) bằng cách chia nhỏ không gian đó thành các vùng con nhỏ hơn. Mỗi node trong Quad Tree có tối đa 4 node con, tương ứng với việc chia vùng hiện tại thành 4 phần bằng nhau (thường là các hình chữ nhật hoặc vuông)
Các hoạt động của Quad tree
Example
1[
2 [1, 1, 0, 0],
3 [1, 1, 0, 0],
4 [1, 1, 0, 0],
5 [1, 1, 0, 0]
6]Hình dung cấu trúc cây
1 [Root]
2 / | | \
3 1 0 1 0Problem
Bài toán yêu cầu xây dựng một cây Quad-tree từ một ma trận vuông chỉ gồm các số 0 và 1. Quad tree là cây mà mỗi node có tối đa 4 node con, dùng để chia nhỏ vùng dữ liệu 2D
Approach
false )val (true nếu vùng toàn 1, false nếu vùng toàn 0), isLeaf , và 4 node conCác bước chính