深度优先遍历和广度优先遍历

dsfNO.112 路径总和
路径和系列问题可以用DFS来解决，BFS求最短路径问题
法一：DFS
root不存在false；root.left and root.right为空：root.val == targetSum;
（一定要判断到叶子节点，左右子树同时为空才是叶子节点）注意此处是root.val == target而不是root = target
  向下递归左右子树self.hasPath(root.left, targetSum-root.val) or self.hasPath(root.right, targetSum-root.val) 
法二：栈迭代
空：false; stack[], stack.append((root, root.val)) 此处pop方法只有一个参数，所以需要加两层括号
栈不空时：当前节点， path= stack.pop()
左子树不空 & 右子树不空 and path == targetSum :return True
左子树存在：stack.append(node.left, path + node.left.val) // 注意后面更新的是node.left而不是root.left
右子树存在：stack.append(node.right, path + node.right.val)

NO.113 路径总和II
法一DFS:
思路同上，定义DFS函数：如果root不存在返回，左子树为空&右子树为空&target==root.val：将当前节点添加到路径里，并将路径添加到最后列表里。
这题需要返回所有路径，而不是只是判断是否存在路径。建立一个列表，添加路径节点。最后将所有路径存在另外的列表里返回
def dfs(root, targetSum, path:List): 
path += [root.val]
ans.append(path)
  dfs(root.left, targetSum - roo.val, path + [root.val]
ans = []
dfs(root, targetSum, [])
法二：迭代栈
方法与前一道题类似，添加ans = []保存所有路径， path[] 保存单个路径
stack = [(root, root.val, [root.val])]
node, sum, path = stack.pop()

注意：用递归法时，每次用的是根节点root，因为每次都相当于一棵树； 用迭代法时，每次用当前节点node， 因为节点一直在变。 
113题比112题加了一个路径，其他类似
113题法一中要不停递归，需递归到最后才是结果，所以要path += [roo.val], 然后ans.append(path); 
   法二用栈，每次到叶子就是一条结果，所以直接ans.append(path)就行,。

No.124 二叉树中的最大路径和
设置全局变量存储最大路径和，不断递归搜索每个子树更新该变量：self.maxSum = float('-inf')
if root is None: return 0
计算左边分支最大值，如果值为负数不如不选择: left = max(0, dfs(root.left))
计算右边分支最大值，如果为负值不如不选择: right 
left->root->right作为路径与已经存在的最大值比较: self.maxSum = max(self.maxSum, root.val + left + right)
返回经过root的单边最大分支：return root.val + max(left, right)
dfs(root)
return self.maxSum

NO.200 岛屿问题
线性扫描整个网格找到第一个‘1’，然后以该节点开始启动深度优先遍历，将访问过的节点标为‘0’。在整个扫描过程中启动深度优先遍历方法
的次数就是岛屿数量。
深度优先遍历沿着一个方向走到尽头，然后换其他方向搜索。本题有4个方向
def dfs(r,c):
  grid[r][c] = '2'
  if r-1 >= 0 and grid[r-1][c] == '1':#上一行
    dfs(r-1, c)
  if r+1 < m and grid[r+1][c] == '1':#下一行
    dfs(r+1, c)
  if c-1 >= 0 and grid[r][c-1] == '1':左一列
    dfs(r, c-1)
  if C+1 >= 0 and grid[r][c+1] == '1':右一列
    dfs(r, c+1)

if grid is None:
return 0
m = len(grid), n = len(grid[0]), count = 0
for i in range(m):
  for j in range(n):
    if grid[i][j] == '1':
      count += 1
      dfs(i,j)
return count

No.305 岛屿数量II
需要会员，暂时跳过