Algorithm/Leetcode/ConstructQuadTree.cs at master · iwiniwin/Algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
/*
题目名称：
建立四叉树

题目描述：
给你一个 n * n 矩阵 grid ，矩阵由若干 0 和 1 组成。请你用四叉树表示该矩阵 grid 。
你需要返回能表示矩阵的 四叉树 的根结点。
注意，当 isLeaf 为 False 时，你可以把 True 或者 False 赋值给节点，两种值都会被判题机制 接受
我们可以按以下步骤为二维区域构建四叉树：
如果当前网格的值相同（即，全为 0 或者全为 1），将 isLeaf 设为 True ，将 val 设为网格相应的值，并将四个子节点都设为 Null 然后停止。
如果当前网格的值不同，将 isLeaf 设为 False， 将 val 设为任意值，然后如下图所示，将当前网格划分为四个子网格。
使用适当的子网格递归每个子节点。

示例：
输入：grid = [[0,1],[1,0]]
输出：[[0,1],[1,0],[1,1],[1,1],[1,0]]

代码结构：
public class Solution {
    public Node Construct(int[][] grid) {

    }
}

题目链接：
https://leetcode-cn.com/problems/construct-quad-tree/
*/
using System;
using System.Collections.Generic;
namespace ConstructQuadTree {

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

    class Solution {

        /// <summary>
        /// 解法，递归
        /// 基本思路：
        /// 首先判断矩阵中的所有值是否相等，如果相等，则为叶子节点，直接返回
        /// 否则
        ///     1. 提取矩阵的上左部分，重复上述步骤，计算上左节点
        ///     1. 提取矩阵的上右部分，重复上述步骤，计算上右节点
        ///     1. 提取矩阵的下左部分，重复上述步骤，计算下左节点
        ///     1. 提取矩阵的下右部分，重复上述步骤，计算上右节点
        /// </summary>

        public Node Construct(int[][] grid) {
            return ConstructImple(grid, 0, grid[0].Length - 1, 0, grid.Length - 1);
        }

        public Node ConstructImple(int[][] grid, int left, int right, int top, int bottom) {
            if(left > right || top > bottom) return null;
            if(IsLeaf(grid, left, right, top, bottom)) {
                return new Node(grid[top][left] == 1 ? true : false, true);
            }
            int delta = (right - left) / 2;
            Node node = new Node(true, false);
            node.topLeft = ConstructImple(grid, left, left + delta, top, top + delta);
            node.topRight = ConstructImple(grid, left + delta + 1, right, top, top + delta);
            node.bottomLeft = ConstructImple(grid, left, left + delta, top + delta + 1, bottom);
            node.bottomRight = ConstructImple(grid, left + delta + 1, right, top + delta + 1, bottom);
            return node;
        }

        public bool IsLeaf(int[][] grid, int left, int right, int top, int bottom) {
            int ret = grid[top][left];
            for(int i = top; i <= bottom; i ++) {
                for(int j = left; j <= right; j ++) {
                    if(grid[i][j] != ret) {
                        return false;
                    }
                }
            }
            return true;
        }

        public void Print(Node root) {
            Console.Write("[");
            Queue<Node> queue = new Queue<Node>();
            queue.Enqueue(root);
            while(queue.Count > 0) {
                Node node = queue.Dequeue();
                if(node == null) {
                    Console.Write("null");
                }else{
                    Console.Write("[" + (node.isLeaf ? 1 : 0) + "," + (node.val ? 1 : 0) + "]");
                    queue.Enqueue(node.topLeft);
                    queue.Enqueue(node.topRight);
                    queue.Enqueue(node.bottomLeft);
                    queue.Enqueue(node.bottomRight);
                }
                if(queue.Count > 0)
                    Console.Write(",");
            }
            Console.WriteLine("]");
        }

        public void Test() {
            int[][] grid = new int[][]{
                new int[]{0, 1},
                new int[]{1, 0}
            };

            // grid = new int[][]{
            //     new int[]{0}
            // };

            // grid = new int[][]{
            //     new int[]{1, 1, 1, 1, 0, 0, 0, 0},
            //     new int[]{1, 1, 1, 1, 0, 0, 0, 0},
            //     new int[]{1, 1, 1, 1, 1, 1, 1, 1},
            //     new int[]{1, 1, 1, 1, 1, 1, 1, 1},
            //     new int[]{1, 1, 1, 1, 0, 0, 0, 0},
            //     new int[]{1, 1, 1, 1, 0, 0, 0, 0},
            //     new int[]{1, 1, 1, 1, 0, 0, 0, 0},
            //     new int[]{1, 1, 1, 1, 0, 0, 0, 0},
            // };

            // grid = new int[][]{
            //     new int[]{1, 1},
            //     new int[]{1, 1}
            // };

            // grid = new int[][]{
            //     new int[]{1, 1, 0, 0},
            //     new int[]{1, 1, 0, 0},
            //     new int[]{0, 0, 1, 1},
            //     new int[]{0, 0, 1, 1}
            // };

            // grid = new int[][]{
            //     new int[]{1, 1, 0, 0},
            //     new int[]{0, 0, 1, 1},
            //     new int[]{1, 1, 0, 0},
            //     new int[]{0, 0, 1, 1}
            // };

            Print(Construct(grid));
        }
    }
}