时间轴

2025-12-01

init

题目：

P427 建立四叉树

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

分治思想：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#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);
	}
};