Construct Quad Tree

2차원 정수 벡터를 받아 이 그리드를 해석하여

topLeft, topRight, bottomLeft, bottomRight들을 차일드로 가지는 쿼드 트리를 구축하는 문제

노드에는 4개의 차일드 말고도 val과 isLeaf 불리언 값을 가지고 있는데

isLeaf는 말그대로 노드가 트리의 리프 노드인지 알려주는 값이며,

val은 트리가 그리드에서 1 값을 가지고 있는지 아닌지를 알려주는 값이다.

/*
// Definition for a QuadTree node.
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;
        top Right = 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;
    }
};
*/

class Solution {
public:
    Node* construct(vector<vector<int>>& grid) {
        return ConstructRecussive(0, 0, grid.size(), grid);
    }
private:
    Node* ConstructRecussive(int row, int col, int length, vector<vector<int>>& grid)
    {
        if (length == 1)
        {
            return new Node((grid[row][col] == 1), true);
        }

        bool isLeaf{true};
        for (int i = row; (i < row + length) && isLeaf; ++i)
        {
            for (int j = col; j < col + length; ++j)
            {
                if (grid[i][j] != grid[row][col])
                {
                    isLeaf = false;
                    break;
                }
            }
        }

        if (isLeaf)
        {
            return new Node((grid[row][col] == 1), true);
        }

        int halfLength{length >> 1};
        int rightUpRow{row};
        int rightUpCol{col + halfLength};
        int leftDownRow{row + halfLength};
        int leftDowncol{col};
        int rightDownRow{row + halfLength};
        int rightDownCol{col + halfLength};

        Node* leftUp = ConstructRecussive(row, col, halfLength, grid);
        Node* rightUp = ConstructRecussive(rightUpRow, rightUpCol, halfLength, grid);
        Node* leftDown = ConstructRecussive(leftDownRow, leftDowncol, halfLength, grid);
        Node* rightDown = ConstructRecussive(rightDownRow, rightDownCol, halfLength, grid);

        return new Node((leftUp->val || rightUp->val || leftDown->val || rightDown->val), 
                        false, leftUp, rightUp, leftDown, rightDown);
    }
};