力扣爆刷第170天之TOP200五连刷116-120（对角线遍历、完全性检验、循环依赖）

力扣爆刷第170天之TOP200五连刷116-120（对角线遍历、完全性检验、循环依赖）

一、LCR 155. 将二叉搜索树转化为排序的双向链表

题目链接：https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/description/
思路：本题是让将二叉搜索树转化为排序的双向链表，返回最小节点的指针，其实很简单。
1、首先理解题目的意思，就是想让你把二叉搜索树变成一个从小到大排序的双向链表。
2、排序可以利用二叉搜索树的特点，使用中序遍历，即可得到升序序列。
3、具体如何原地组装成双向链表呢？其实只需要用一个指针head记录下中序遍历的开始位置，另一个指针pre记录中序遍历的前一个节点，这样每次遍历到中序的位置时，只需要让当前节点与前一个节点pre，建立前驱后继关系即可。
4、如果构成循环链表，当中序遍历完成后，pre节点正好记录的是最后一个遍历过的节点，即可与之前记录的head节点建立前驱后继关系。

/*
// Definition for a Node.
class Node {public int val;public Node left;public Node right;public Node() {}public Node(int _val) {val = _val;}public Node(int _val,Node _left,Node _right) {val = _val;left = _left;right = _right;}
};
*/
class Solution {Node head, pre;public Node treeToDoublyList(Node root) {if(root == null) return root;traverse(root);head.left = pre;pre.right = head;return head;}void traverse(Node root) {if(root == null) return ;traverse(root.left);if(head == null) {head = root;pre = root;}else{pre.right = root;root.left = pre;pre = root;}traverse(root.right);}
}

二、498. 对角线遍历

题目链接：https://leetcode.cn/problems/diagonal-traverse/description/
思路：本题要求对角线遍历，其实是一个很直观的过程，在每一次遍历的过程中，行与列要不一个增加要不一个减少，我们要做的只是每次对角线遍历，翻转行与列，维护一个同一个的形式，把这种来回反方向的遍历，转化成单一方向的遍历。
1、首先需要确定对角线遍历的次数，即m+n次。
2、观察每一趟遍历，第一趟，x减少，y增加，第二趟，x增加，y减少，这个其实是交替进行的，那么我们可以通过一个标志位flag来控制，让flag=true时，我们就从左下往右上遍历，flag=false时，我们就从右上往左下遍历，由此就可以利用flag，来交换x与y，让x一直减少，让y一直增加，res[k++] = flag ? mat[x][y] : mat[y][x];这样就便于维护x和y的上下限，方便控制边界条件。
3、x和y还有一个依赖关系，x每超出边界时可以一直++，y的值为总对角线数减去x的个数，这样就可以控制起始位置。

class Solution {public int[] findDiagonalOrder(int[][] mat) {boolean flag = true;int m = mat.length, n = mat[0].length;int[] res = new int[m*n];int k = 0;for(int i = 0; i < m + n; i++) {int pm = flag ? m : n;int pn = flag ? n : m;int x = (i < pm) ? i : pm - 1;int y = i - x;while(x >= 0 && y < pn) {res[k++] = flag ? mat[x][y] : mat[y][x];x--;y++;}flag = !flag;}return res;}
}

三、958. 二叉树的完全性检验

题目链接：https://leetcode.cn/problems/check-completeness-of-a-binary-tree/description/
思路：本题要求验证一棵树是否是完全二叉树，其实就是要求理解完全二叉树的特性，完全二叉树一定是满节点的，并且在最后一层靠左边的节点都是满的，右边的可能空出来。
1、知道完全二叉树的特性，并且利用这个特性。
2、如何利用呢？只需要找到节点空缺的位置即可，即当前行，左边有空节点，右边有实节点，这要出现这种情况，即非完全二叉树。
3、采用什么方式遍历呢？针对第二天，采用层序遍历最为合适，往Queue里可以添加null节点，如果当前遍历过null节点了，后续出队的有非null节点即说明非完全二叉树。

class Solution {public boolean isCompleteTree(TreeNode root) {Deque<TreeNode> queue = new LinkedList<>();queue.add(root);boolean flag = true;while(!queue.isEmpty()) {int size = queue.size();for(int i = 0; i < size; i++) {TreeNode node = queue.poll();if(node == null) flag = false;else{if(!flag) return false;queue.add(node.left);queue.add(node.right);}}}return true;}}

四、210. 课程表 II

题目链接：https://leetcode.cn/problems/course-schedule-ii/description/
思路：本题是一个有向图，求拓扑排序，这个方式是有很多的，可以把它当成树进行遍历，后序位置进行收集，也可以采用入度为0进行处理。
解法一：基于拓扑的方式进行遍历，记录所有节点的入度，从入度为0的节点开始遍历，把from节点对应的to节点扣减入度，为0就加入队列，队列遍历完毕就OK了。

class Solution {public int[] findOrder(int numCourses, int[][] prerequisites) {int[] res = new int[numCourses];int[] indeg = new int[numCourses];List<Integer>[] list = builderGraph(numCourses, prerequisites, indeg);LinkedList<Integer> queue = new LinkedList<>();for(int i = 0; i < numCourses; i++) {if(indeg[i] == 0) queue.add(i);}int k = 0;while(!queue.isEmpty()) {int from = queue.poll();res[k++] = from;for(int i = 0; i < list[from].size(); i++) {int to = list[from].get(i);indeg[to]--;if(indeg[to] == 0) queue.add(to);}}if(k != numCourses) return new int[]{};return res;}List<Integer>[] builderGraph(int numCourses, int[][] prerequisites, int[] indeg) {List<Integer>[] list = new LinkedList[numCourses];for(int i = 0; i < numCourses; i++) list[i] = new LinkedList();for(int[] temp : prerequisites) {list[temp[1]].add(temp[0]);indeg[temp[0]]++;}return list;}
}

解法二：采用类似树的后序遍历的位置进行搜集。

class Solution {boolean[] visited;boolean[] onPaths;boolean hasCycle;List<Integer> list;public int[] findOrder(int numCourses, int[][] prerequisites) {visited = new boolean[numCourses];onPaths = new boolean[numCourses];list = new ArrayList<>();List<Integer>[] graph = buildGraph(numCourses, prerequisites);for (int i = 0; i < numCourses; i++) {travers(graph, i);}if (hasCycle) {return new int[]{};}int[] res = new int[numCourses];for (int i = 0; i < list.size(); i++) {res[i] = list.get(i);}return res;}void travers(List<Integer>[] graph, int i) {if (onPaths[i]) {hasCycle = true;}if (visited[i] || hasCycle) {return;}onPaths[i] = true;visited[i] = true;for (Integer j : graph[i]) {travers(graph, j);}list.add(i);onPaths[i] = false;}List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {List<Integer>[] graph = new ArrayList[numCourses];for (int i = 0; i < numCourses; i++) {graph[i] = new ArrayList<>();}for (int[] ints : prerequisites) {graph[ints[0]].add(ints[1]);}return graph;}}

五、74. 搜索二维矩阵

题目链接：https://leetcode.cn/problems/search-a-2d-matrix/description/
思路：本题每一行都单调递增，然后前一行最后一个数大于当前行第一个数，让找一个数是否位于其中。
1、有很多种解法，第一种，先确定是哪一行，然后直接二分查找。
2、从右上加开始进行DFS遍历，target大于当前值向下，小于向左。

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length, n = matrix[0].length;int flag = -1;for(int i = 0; i < m; i++) {if(target >= matrix[i][0] && target <= matrix[i][n-1]) {flag = i;break;}}if(flag == -1) return false;int[] nums = matrix[flag];int left = 0, right = n-1;while(left <= right) {int mid = left + (right - left) / 2;if(nums[mid] == target) return true;else if(nums[mid] > target) right = mid-1;else left = mid+1;}return false;}
}