Construct Quad Tree.cpp

/*
// 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;
        }
    }
};