Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 427. Construct Quad Tree

---

題目：


解答：

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

class Solution {
public:
    Node* construct(vector<vector<int>>& grid) {
        return build(grid, 0, 0, grid.size());
    }

    Node* build(vector<vector<int>>& grid, int r, int c, int size) {
        bool same = true;
        int v = grid[r][c];

        for (int i = r; i < r + size; ++i) {
            for (int j = c; j < c + size; ++j) {
                if (grid[i][j] != v) {
                    same = false;
                    break;
                }
            }

            if (!same) {
                break;
            }
        }

        if (same) {
            return new Node(v, true);
        }

        int h = size >> 1;

        Node* n = new Node(true, false);
        n->topLeft = build(grid, r, c, h);
        n->topRight = build(grid, r, c + h, h);
        n->bottomLeft = build(grid, r + h, c, h);
        n->bottomRight = build(grid, r + h, c + h, h);

        return n;
    }
};