Construct Quad Tree — LeetCode 427 Python Solution
MediumTreeArrayDivide and ConquerMatrix
- Problem
- #427
- Pattern
- Matrix and Grid
- Reading time
- 6 min
- Source
- leetcode.com
The problem
Given a n * n matrix grid of 0's and 1's only. We want to represent grid with a Quad-Tree.
Example
class Node {
public boolean val;
public boolean isLeaf;
public Node topLeft;
public Node topRight;
public Node bottomLeft;
public Node bottomRight;
}Python solution
Python
"""
# Definition for a QuadTree node.
class Node:
def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):
self.val = val
self.isLeaf = isLeaf
self.topLeft = topLeft
self.topRight = topRight
self.bottomLeft = bottomLeft
self.bottomRight = bottomRight
"""
class Solution:
def construct(self, grid: List[List[int]]) -> 'Node':
def dfs(a, b, c, d):
zero = one = 0
for i in range(a, c + 1):
for j in range(b, d + 1):
if grid[i][j] == 0:
zero = 1
else:
one = 1
isLeaf = zero + one == 1
val = isLeaf and one
if isLeaf:
return Node(grid[a][b], True)
topLeft = dfs(a, b, (a + c) // 2, (b + d) // 2)
topRight = dfs(a, (b + d) // 2 + 1, (a + c) // 2, d)
bottomLeft = dfs((a + c) // 2 + 1, b, c, (b + d) // 2)
bottomRight = dfs((a + c) // 2 + 1, (b + d) // 2 + 1, c, d)
return Node(val, isLeaf, topLeft, topRight, bottomLeft, bottomRight)
return dfs(0, 0, len(grid) - 1, len(grid[0]) - 1)Complexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(h) auxiliary |
Pattern: Matrix and Grid
Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 427. Construct Quad Tree is filed here because LeetCode tags it Matrix, which is the vocabulary this hub collects.
The matrix and grid guide has the Python template for the pattern and the 216 LeetCode problems that use it.
Related problems
LeetCode 108Convert Sorted Array to Binary Search TreeEasyLeetCode 109Convert Sorted List to Binary Search TreeMediumLeetCode 558Logical OR of Two Binary Grids Represented as Quad-TreesMediumLeetCode 2509Cycle Length Queries in a TreeHardLeetCode 450Delete Node in a BSTMediumLeetCode 700Search in a Binary Search TreeEasy
On a study list
This problem is on Top Interview 150.
Frequently asked questions
- How hard is LeetCode 427. Construct Quad Tree?
- LeetCode 427. Construct Quad Tree is rated Medium on LeetCode.
- What is the time complexity of LeetCode 427. Construct Quad Tree?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 427. Construct Quad Tree?
- The Python solution on this page uses O(h) auxiliary space.
- What topics does LeetCode 427. Construct Quad Tree cover?
- LeetCode 427. Construct Quad Tree is tagged Tree, Array, Divide and Conquer and Matrix on LeetCode.