hot 100深度优先

98. 验证二叉搜索树
    给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

采用中序遍历，如果是二叉搜索树，那么采用中序遍历的结果应该是递增的。设置一个pre代表前一个结点的大小，如果前一个结点大于后一个节点，则不是。

class Solution {
    
    long pre = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
    
        return digui(root);
    }
    public boolean digui(TreeNode root){
    
        if(root == null){
    
            return true;
        }
        boolean left = digui(root.left);
        if(root.val <= pre){
    
            return false;
        }
        pre = root.val;
        boolean right = digui(root.right);
        return left&&right;
        
        
    }
}

101. 对称二叉树
     给你一个二叉树的根节点 root ， 检查它是否轴对称。

class Solution {
    
    public boolean isSymmetric(TreeNode root) {
    
        if(root.left == null && root.right == null){
    
            return true;
        }
        else if(root.left == null || root.right == null){
    
            return false;
        }
        return digui(root.left,root.right);
    }
    public boolean digui(TreeNode left, TreeNode right){
    
        if(left == null && right == null){
    
            return true;
        }
        else if(left == null || right == null){
    
            return false;
        }
        if(left.val == right.val){
    
            return digui(left.left,right.right) && digui(left.right,right.left);
        }
        else{
    
            return false;
        }
    }
}

114. 二叉树展开为链表
     给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。

示例 1：

输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]

简单粗暴的方法：先序遍历树，把node存在list中，再遍历list构建链表

class Solution {
    
    public void flatten(TreeNode root) {
    
        List<TreeNode> list = new ArrayList<>();
        
        digui(root,list);
        for(int i = 1; i < list.size();i++){
    
            root.right = list.get(i);
            root.left = null;
            root = root.right;
        }
        

    }
    public void digui(TreeNode root,List list){
    
        if(root == null){
    
            return;
        }
        list.add(root);
        digui(root.left,list);
        digui(root.right,list);
    }
}

200. 岛屿数量
     给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [
[“1”,“1”,“1”,“1”,“0”],
[“1”,“1”,“0”,“1”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“0”,“0”,“0”]
]
输出：1

深度优先搜索，找到1所在的位置，然后向上下左右遍历，遍历之前要把当前的1置为0避免重复，当把一块1全部置为0后，再去找下一个存在的1.

class Solution {
    
    public int numIslands(char[][] grid) {
    
        int row = grid.length;
        int col = grid[0].length;
        int res = 0;
        for(int i = 0; i < row; i++){
    
            for(int j = 0; j < col;j++){
    
                if(grid[i][j] == '1'){
    
                    digui(grid,i,j);
                    res++;
                }
            }
        }
        return res;
       
    }
    public void digui(char[][] grid, int row, int col){
    
        if(row == grid.length || col == grid[0].length || col < 0 || row < 0){
    
            return;
        }
        if(grid[row][col] == '1'){
    
            grid[row][col] = '0';
            digui(grid,row+1,col);
            digui(grid,row-1,col);
            digui(grid,row,col+1);
            digui(grid,row,col-1);
            
        }
    }
}

207. 课程表(拓扑排序)
     你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

采用的是广度优先加拓扑排序
维护两个表，一个是邻接矩阵，表示每个点有哪些点和这个点连接，在此题中维护了一个list，list包含有课程数个小list，小list在大list中的位置表示这是哪个点的邻接矩阵。
除此之外还维护了一个入度表，表示每个点的入读为多少

算法流程为，找到入读为0的点，这个点就是源头，加入到queue里，找到这个点所有的邻接点，将他们的入度减一，如果入度为0了，就加入queue里。相当于每次都遍历入度为0的点，将其删去，将其相邻的点入度减一，重复这个过程，知道图中不存在点。

class Solution {
    
    public boolean canFinish(int numCourses, int[][] prerequisites) {
    
        List<List<Integer>> adjacency = new ArrayList<>();
        int[] inorder = new int[numCourses];
        for(int i = 0; i < numCourses; i++){
    
            adjacency.add(new ArrayList());
        }
        for(int i = 0 ; i < prerequisites.length; i++){
    
            adjacency.get(prerequisites[i][1]).add(prerequisites[i][0]);
            inorder[prerequisites[i][0]]++;
        }
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i < numCourses; i++){
    
            if(inorder[i] == 0){
    
                queue.add(i);
            }
        }
        int courses = numCourses;
        while(!queue.isEmpty()){
    
            int course = queue.poll();
            for(int num : adjacency.get(course)){
    
                inorder[num]--;
                if(inorder[num] == 0){
    
                    queue.add(num);
                }
            }
            courses--;
        }
        return courses == 0 ? true : false;
    }
}

226. 翻转二叉树
     给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

class Solution {
    
    public TreeNode invertTree(TreeNode root) {
    
        digui(root);
        return root;
    }
    public void digui(TreeNode root){
    
        if(root == null){
    
            return;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        digui(root.left);
        digui(root.right);
    }
}

236. 二叉树的最近公共祖先
     给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

采用递归，获取每个节点的左节点和右节点，这时候分成四种情况：

1. root本身属于p/q/null，则直接返回root
2. root左右节点都不是null，说明pq分居两侧，直接返回root
3. root其中一边不是null，则返回不是null的那一个节点
4. 两边都是null，说明pq不在此节点下，直接返回null

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
    
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    
        return digui(root,p,q);
    }
    public TreeNode digui(TreeNode root, TreeNode p, TreeNode q){
    
        if(root == null || root.val == p.val || root.val == q.val){
    
            return root;
        }
        TreeNode left = digui(root.left,p,q);
        TreeNode right = digui(root.right,p,q);
        if(left != null && right != null){
    
            return root;
        }
        if(left == null){
    
            return right;
        }
        if(right == null){
    
            return left;
        }
        else{
    
            return null;
        }
    }
}