427.Construct Quad Tree

tags: Medium,Array,Divide and Conquer,Tree,Matrix

427. Construct Quad Tree

題目描述

Given a n * n matrix grid of 0's and 1's only. We want to represent the grid with a Quad-Tree.

Return the root of the Quad-Tree representing the grid.

Notice that you can assign the value of a node to True or False when isLeaf is False, and both are accepted in the answer.

A Quad-Tree is a tree data structure in which each internal node has exactly four children. Besides, each node has two attributes:

• val: True if the node represents a grid of 1's or False if the node represents a grid of 0's.
• isLeaf: True if the node is leaf node on the tree or False if the node has the four children.

class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;
}

We can construct a Quad-Tree from a two-dimensional area using the following steps:

If the current grid has the same value (i.e all 1's or all 0's) set isLeaf True and set val to the value of the grid and set the four children to Null and stop.
If the current grid has different values, set isLeaf to False and set val to any value and divide the current grid into four sub-grids as shown in the photo.
Recurse for each of the children with the proper sub-grid.

If you want to know more about the Quad-Tree, you can refer to the wiki.

Quad-Tree format:

The output represents the serialized format of a Quad-Tree using level order traversal, where null signifies a path terminator where no node exists below.

It is very similar to the serialization of the binary tree. The only difference is that the node is represented as a list [isLeaf, val].

If the value of isLeaf or val is True we represent it as 1 in the list [isLeaf, val] and if the value of isLeaf or val is False we represent it as 0.

範例

Example 1:

Input: grid = [[0,1],[1,0]]
Output: [[0,1],[1,0],[1,1],[1,1],[1,0]]
Explanation: The explanation of this example is shown below:
Notice that 0 represnts False and 1 represents True in the photo representing the Quad-Tree.

Example 2:

Input: grid = [[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0]]
Output: [[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]
Explanation: All values in the grid are not the same. We divide the grid into four sub-grids.
The topLeft, bottomLeft and bottomRight each has the same value.
The topRight have different values so we divide it into 4 sub-grids where each has the same value.
Explanation is shown in the photo below:

Constraints:

• n == grid.length == grid[i].length
• n == 2^x where 0 <= x <= 6

解答

C++

思路:

1. 把2d array分成四個區塊來做Quad-tree, 某一個區塊若值都相同, 則val=該值, leaf為true, 不同則leaf為false, val可隨意填, 且還要進一步去再細分四個區塊, 直到所有leaf node的leaf值為true
2. 遞迴建構樹, 確認目前區塊值是否全一致, 一致則返回, 不一致繼續遞迴

class Solution {
public:
    Node* helper(vector<vector<int>>& grid, int row, int col, int n)
    {
        bool is_same = true;
        for(int i = row; i < row+n; i++)
        {
            for(int j = col; j < col+n; j++)
            {
                if(grid[i][j] != grid[row][col])
                {
                    is_same = false;
                    break;
                }
            }
        }
        
        if(is_same)
            return new Node(grid[row][col], true);
        else
        {
            Node* cur_node = new Node(0, false);
            n /= 2;
            cur_node->topLeft = helper(grid, row, col, n);
            cur_node->topRight = helper(grid, row, col+n, n);
            cur_node->bottomLeft = helper(grid, row+n, col, n);
            cur_node->bottomRight = helper(grid, row+n, col+n, n);
            return cur_node;
        }
    }
    Node* construct(vector<vector<int>>& grid) {
        return helper(grid, 0, 0, grid.size());
    }
};

Time:

$O(n^2\ast logn)$ 每次確認n*n區塊內是否全相同, 最多做

$logn$次
Extra Space:

$O(n^2)$

XD Feb 27, 2023

思路

將leaf獨立出來，然後利用遞迴，只需要檢查四個孩子是否相同就好。

Node* zero = new Node(false, true);
Node* one = new Node(true, true);

class Solution {
public:
    Node* dfs(vector<vector<int>>& grid, int i, int j, int n) {
        if (n == 0) return grid[i][j] == 0 ? zero : one;
        auto topLeft = dfs(grid, i, j, n >> 1);
        auto topRight = dfs(grid, i, j + n, n >> 1);
        auto bottomLeft = dfs(grid, i + n, j, n >> 1);
        auto bottomRight = dfs(grid, i + n, j + n, n >> 1);
        if (topLeft == topRight && bottomLeft == bottomRight && topLeft == bottomLeft) {
            return topLeft;
        }
        return new Node(false, false, topLeft, topRight, bottomLeft, bottomRight);
    }
    Node* construct(vector<vector<int>>& grid) {
        return dfs(grid, 0, 0, grid.size() >> 1);
    }
};

Time:

$O(n^2)$
Space:

$O(\log n)$

Yen-Chi ChenMon, Feb 27, 2023

Python

class Solution:
    def construct(self, grid: List[List[int]]) -> 'Node':
        zero = Node(False, True, None, None, None, None)
        one = Node(True, True, None, None, None, None)

        def dfs(i, j, n):
            if n == 0: return zero if grid[i][j] == 0 else one
            tl = dfs(i, j, n >> 1)
            tr = dfs(i, j + n, n >> 1)
            bl = dfs(i + n, j, n >> 1)
            br = dfs(i + n, j + n, n >> 1)
            if tl == tr == bl == br:
                return tl
            return Node(False, False, tl, tr, bl, br)
        
        return dfs(0, 0, len(grid) >> 1)

Yen-Chi ChenMon, Feb 27, 2023

Reference

回到題目列表