Classic 150 Interview Questions P427 Construct Quad Tree

---

Timeline

Timeline

2025-12-01

init

Divide and Conquer

---

Problem:

P427 Construct Quad Tree

https://leetcode.cn/problems/construct-quad-tree/description/?envType=study-plan-v2&envId=top-interview-150

Divide and Conquer approach:

#include <stddef.h>

class Node {
    public:
	bool val;
	bool isLeaf;
	Node *topLeft;
	Node *topRight;
	Node *bottomLeft;
	Node *bottomRight;

	Node()
	{
		val = false;
		isLeaf = false;
		topLeft = NULL;
		topRight = NULL;
		bottomLeft = NULL;
		bottomRight = NULL;
	}

	Node(bool _val, bool _isLeaf)
	{
		val = _val;
		isLeaf = _isLeaf;
		topLeft = NULL;
		topRight = NULL;
		bottomLeft = NULL;
		bottomRight = NULL;
	}

	Node(bool _val, bool _isLeaf, Node *_topLeft, Node *_topRight, Node *_bottomLeft, Node *_bottomRight)
	{
		val = _val;
		isLeaf = _isLeaf;
		topLeft = _topLeft;
		topRight = _topRight;
		bottomLeft = _bottomLeft;
		bottomRight = _bottomRight;
	}
};

#include <vector>
#include <climits>
#include <stddef.h>
using std::vector;

class Solution {
private:
	Node *buildQuadTree(vector<vector<int> > &grid, int si, int sj, int size)
	{
		int i, j;
		int val = grid[si][sj];
		bool is_leaf = true;

		for (i = si; i < si + size; i++) {
			for (j = sj; j < sj + size; j++) {
				if (grid[i][j] != val) {
					is_leaf = false;
					break;
				}
			}
		}

		Node *root = new Node;
		if (is_leaf) {
			root->topLeft = NULL;
			root->topRight = NULL;
			root->bottomLeft = NULL;
			root->bottomRight = NULL;
			root->val = val;
		} else {
			root->topLeft = buildQuadTree(grid, si, sj, size / 2);
			root->topRight = buildQuadTree(grid, si, sj + size / 2, size / 2);
			root->bottomLeft = buildQuadTree(grid, si + size / 2, sj, size / 2);
			root->bottomRight = buildQuadTree(grid, si + size / 2, sj + size / 2, size / 2);
			root->val = INT_MAX;
		}
		root->isLeaf = is_leaf;

		return root;
	}

public:
	Node *construct(vector<vector<int> > &grid)
	{
		int i, j, n = grid.size();
		return buildQuadTree(grid, 0, 0, n);
	}
};