Construct Quad Tree
The key idea
A region becomes a single leaf only when every cell in it shares one value. Otherwise split it into four equal quadrants and recurse on each. The recursion bottoms out at 1x1 cells, which are always uniform, so it always terminates.
Problem
You are given an n x n matrix grid of 0s and 1s. Return the root of a Quad-Tree that represents grid.
A Quad-Tree is a tree where each internal node has exactly four children: topLeft, topRight, bottomLeft, and bottomRight. Each node holds two values: val (the value of the region it covers, true for 1 and false for 0) and isLeaf (true when the node is a leaf, false when it has children).
Build the tree by this rule: if the current region holds all the same value, make it a single leaf node with that val. Otherwise split the region into four equal sub-regions and recurse on each. It is guaranteed that n is a power of two, so every region can be split cleanly until it reaches 1 x 1 cells.
Constraints
n == grid.length == grid[i].lengthn == 2^xwhere0 <= x <= 6
Examples
Input: grid = [[0,1],[1,0]]
Output: [[0,1],[1,0],[1,1],[1,0],[1,0]]
Input: grid = [[1,1,0,0],[1,1,0,0],[0,0,1,1],[0,0,1,1]]
Output: [[0,1],[1,1],[1,0],[1,0],[1,1]]
Input: grid = [[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0]]
Output: [[0,1],[1,1],[0,1],[1,1],[1,0],[null,null],[null,null],[null,null],[null,null],[1,0],[1,0],[1,1],[1,1],[1,0],[1,0],null,null,null,null,[1,1],[1,1],[1,1],[1,1],null,null,null,null,[1,1],[1,1],[1,1],[1,1]]
Complexity
Time: O(n^2 log n) Space: O(n^2)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Divide & Conquer problems
- Convert Sorted Array to Binary Search TreeEASY
- Pow(x, n)MEDIUM
- Sort ListMEDIUM