二叉树遍历

前中后序遍历的区别：访问根节点的先后顺序。
递归遍历注意点：注意递归结束的条件（一般是判断节点==nil).

DFS:深度优先策略

①注意空节点（为根节点或者叶子节点的下一层）
②注意叶子节点的处理
③处理当前层需要处理的问题
④递归左右子树
⑤有需要返回的return

BFS：广度优先策略

①注意根节点
②初始化第一层节点，加入队列queue
③循环队列（!queue.isempty），处理队列节点，并判断左右子节点是否为空，然后添加下一层节点到队列，删除当前处理的节

自顶向下

①传入当前层节点与当前层状态（变量）
②空节点问题
③叶子节点问题
④下探入下一层的左右子树，返回①

func pathSum(_ root: Node?, _ sum: Int) -> Bool {
    if root == nil { return false }
    if root?.left == nil && root?.right == nil {
        return root?.val == sum
    }
    return pathSum(root?.left, sum - root!.val) || path(root?.right, sum - root!.val)
}

var ans = 0
// 每下探一层，深度加一
func maximun_d(_ node: TreeNode?, _ depth: Int) {
  // 空节点，没必要继续下探
  if node == nil { return }
    // 下探到最底层，重新比较最大深度
    if (node!.left == nil) && (node!.right == nil) {
        ans = max(ans, depth)
    }
    maximun_d(node?.left, depth + 1)
    maximun_d(node?.right, depth + 1)
}
maximun_d(root, 1)
return ans

自底向上

①空节点问题
②左右子树递归探底
③计算初始问题，并返回结果

// 最大深度
func max_depth(_ root: Node?) -> Int {
    // 空节点，（可能是空根节点或者叶子节点的下一层），返回0
    if root == nil { return 0 }
    var left_depth = 0, right_depth = 0, max_depth = 0
    left_depth = maxi_depth(root?.left)
    right_depth = maxi_depth(root?.right)
    // 每次递归返回一层，深度加1
    max_depth = max(left_depth, right_depth) + 1
    return max_depth
    // 或者
    if root == nil {  return 0  }
    return max(maxDepth(root?.left), maxDepth(root?.right)) + 1
}