[LeetCode]Construct Quad Tree

题目链接

递归地分成四个区间recursively construct即可，注意终止条件。对于可能的叶节点，我们要check所有部位null的子节点都为叶节点并且全为true或者false。时间复杂度O(m * n)，m和n为输入举证的行数和列数。注意comment中记录的几个bug，代码如下：

	/*
	// Definition for a QuadTree node.
	class Node {
	public:
	bool val;
	bool isLeaf;
	Node* topLeft;
	Node* topRight;
	Node* bottomLeft;
	Node* bottomRight;
	Node() {}
	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;
	}
	};
	*/
	class Solution {
	public:
	Node* construct(vector<vector<int>>& grid) {
	int m = grid.size(), n = m? grid[0].size(): 0;
	auto root = createTree(grid, 0, 0, m - 1, n - 1);
	return root;
	}
	private:
	Node* createTree(const vector<vector<int>>& grid, int r1, int c1, int r2, int c2)
	{
	int m = grid.size(), n = m? grid[0].size(): 0;
	if(r1 > r2 || c1 > c2)return nullptr;
	if(r1 == r2 && c1 == c2)
	//bug: make sure four children are nullptr
	return new Node(grid[r1][c1], true, nullptr, nullptr, nullptr, nullptr);
	int midr = r1 + (r2 - r1) / 2, midc = c1 + (c2 - c1) / 2;
	auto topLeft = createTree(grid, r1, c1, midr, midc);
	auto topRight = createTree(grid, r1, midc + 1, midr, c2);
	auto bottomLeft = createTree(grid, midr + 1, c1, r2, midc);
	auto bottomRight = createTree(grid, midr + 1, midc + 1, r2, c2);
	//bug2 : use set instead of cnt/sum to determine if it is leaf
	unordered_set<bool> set;
	if(topLeft){set.insert(topLeft->val);}
	if(topRight){set.insert(topRight->val);}
	if(bottomLeft){set.insert(bottomLeft->val);}
	if(bottomRight){set.insert(bottomRight->val);}
	//bug3: make sure all children are leaf then we can merge them is possible
	if(set.size() == 1 && topLeft && topLeft->isLeaf && topRight && topRight->isLeaf && bottomLeft && bottomLeft->isLeaf && bottomRight && bottomRight->isLeaf)
	{
	delete topLeft;
	delete topRight;
	delete bottomLeft;
	delete bottomRight;
	//bug: make sure four children are nullptr
	return new Node(*(set.begin()), true, nullptr, nullptr, nullptr, nullptr);
	}
	else
	{
	Node* node = new Node(false, false, topLeft, topRight, bottomLeft, bottomRight);
	return node;
	}
	}
	};

view raw Construct Quad Tree.cpp hosted with ❤ by GitHub