Leet Code 四叉樹建立分享

https://leetcode.com/problems/construct-quad-tree/ 四叉樹維基 四叉樹簡介:

好處在做搜尋時比較快。 O(n) -> O(h) // h為樹的高度 //n 為總數

Leet Code 四叉樹建立分享 簡單來說就是用遞迴去跑 8->4->2->1 以此類推

step 1. 判斷是否全 0 or 全 1 如果是 isLeaf = true, reutrn node

step 2. 如果不是把它分成4等份 呼叫遞迴

step 3. 一直到拆分到只剩 1 為止

/*

// Definition for a QuadTree node.

public class Node {

    public bool val;

    public bool isLeaf;

    public Node topLeft;

    public Node topRight;

    public Node bottomLeft;

    public Node bottomRight;

    public Node() {

        val = false;

        isLeaf = false;

        topLeft = null;

        topRight = null;

        bottomLeft = null;

        bottomRight = null;

    }

    

    public Node(bool _val, bool _isLeaf) {

        val = _val;

        isLeaf = _isLeaf;

        topLeft = null;

        topRight = null;

        bottomLeft = null;

        bottomRight = null;

    }

    

    public 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;

    }

}

*/

public class Solution {

    public Node Construct(int[][] grid)

    {

        if (grid == null)

        {

            return null;

        }

        Node root = new Node();

        root = Link(grid);

        return root;

    }

    public Node Link(int[][] grid)

    {

        Node n = new Node();

        if (grid.Length == 1)

        {

            n.val = grid[0][0] == 1;

            n.isLeaf = true;

            return n;

        }

        int size = grid.Length;

        int halfSize = size / 2;

        bool all1 = true;

        bool all0 = true;

        for (int x = 0; x < size; x++)

        {

            for (int y = 0; y < size; y++)

            {

                all0 = all0 && grid[x][y] == 0;

                all1 = all1 && grid[x][y] == 1;

            }

        }

        if (all1)

        {

            n.val = true;

            n.isLeaf = true;

            return n;

        }

        if (all0)

        {

            n.val = false;

            n.isLeaf = true;

            return n;

        }

        int[][] topleft = new int[halfSize][];

        for (int x = 0; x < halfSize; x++)

        {

            for (int y = 0; y < halfSize; y++)

            {

                if (topleft[y] == null)

                {

                    topleft[y] = new int[halfSize];

                }

                topleft[y][x] = grid[y][x];

            }

        }

        n.topLeft = Link(topleft);

        int[][] topRight = new int[halfSize][];

        for (int x = halfSize; x < halfSize * 2; x++)

        {

            for (int y = 0; y < halfSize; y++)

            {

                if (topRight[y] == null)

                {

                    topRight[y] = new int[halfSize];

                }

                topRight[y][x - halfSize] = grid[y][x];

            }

        }

        n.topRight = Link(topRight);

        int[][] bottomLeft = new int[halfSize][];

        for (int x = 0; x < halfSize; x++)

        {

            for (int y = halfSize; y < halfSize * 2; y++)

            {

                if (bottomLeft[y - halfSize] == null)

                {

                    bottomLeft[y - halfSize] = new int[halfSize];

                }

                bottomLeft[y - halfSize][x] = grid[y][x];

            }

        }

        n.bottomLeft = Link(bottomLeft);

        int[][] bottomRight = new int[halfSize][];

        for (int x = halfSize; x < halfSize * 2; x++)

        {

            for (int y = halfSize; y < halfSize * 2; y++)

            {

                if (bottomRight[y - halfSize] == null)

                {

                    bottomRight[y - halfSize] = new int[halfSize];

                }

                bottomRight[y - halfSize][x - halfSize] = grid[y][x];

            }

        }

        n.bottomRight = Link(bottomRight);

        if (n.topLeft == null && n.topRight == null && n.bottomLeft == null && n.bottomRight == null)

        {

            return null;

        }

        else

        {

            if (n.topLeft.val || n.topRight.val || n.bottomLeft.val || n.bottomRight.val)

            {

                n.val = true;

                return n;

            }

            else

            {

                n.val = false;

                return n;

            }

        }

    }

}