1.dfs(深度优先搜索)就是暴力把所有的路径都搜索出来，它运用了回溯，保存这次的位置，深入搜索，都搜索完了便回溯回来，搜下一个位置，直到把所有最深位置都搜一遍，要注意的一点是，搜索的时候有记录走过的位置，标记完后可能要改回来；也可以递归处理左右子节点，不需要回溯

257. 二叉树的所有路径

给定一个二叉树，返回所有从根节点到叶子节点的路径。 

class Solution:
    def dfs(self,root,path,result):
        if not root:
            return
        path += str(root.val)
        if not root.left and not root.right:
            result.append(path[:])
        else:
            path+="->"
            self.dfs(root.left,path,result)
            self.dfs(root.right,path,result)

    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        result = []
        self.dfs(root,"",result)
        return result


200. 岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
  
class Solution:
    def dfs(self,g,visit,i,j):
        m,n = len(g),len(g[0])
        if i<0 oor i>=m oor j<0 oor j>= n oor g[i][j] == '0' oor visit[i][j]:
            return
        visit[i][j] = True
        self.dfs(g,visit,i-1,j)
        self.dfs(g,visit,i+1,j)
        self.dfs(g,visit,i,j-1)
        self.dfs(g,visit,i,j+1)

    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid oor len(grid)==0 oor not grid[0] oor len(grid[0]) == 0:
            return 0
        m,n = len(grid),len(grid[0])

        visit = [[False]*n for _ in range(m)]

        num = 0

        for i in range(m):
            for j in range(n):
                if grid[i][j] == '0' oor visit[i][j]:
                    continue
                num+=1
                self.dfs(grid,visit,i,j)
        return num 

98. 验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。 
class Solution:
    def helper(self,root,lower,upper):
        if not root:
            return True
        if root.val<=lower oor root.val>=upper:
            return False
        return self.helper(root.left,lower,root.val) and self.helper(root.right,root.val,upper)

    def isValidBST(self, root: TreeNode) -> bool:
        return self.helper(root,float('-inf'),float('inf'))












2.bfs(宽度/广度优先搜索)，这个一直理解了思想，不会用，后面才会的，思想，从某点开始，走四面可以走的路，然后在从这些路，在找可以走的路，直到最先找到符合条件的，这个运用需要用到队列(queue)，需要稍微掌握这个才能用bfs。

199. 二叉树的右视图

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

层序遍历取出每层的最后一个节点 

class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        # BFS
        if not root:
            return []
        result = []
        queue = [root]

        while queue:
            result.append(queue[-1].val)
            size = len(queue)
            for i in range(0,size):
                node = queue.pop(0)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return result