二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

二叉树

输入：root = [3,9,20,null,null,15,7]
输出：3

直接去遍历

遍历二叉树，最常见的方式就是使用递归遍历

function maxDeep (root) {
  let result = 0
  let deep = 0
  function travel(root, deep){
    if(root === null) return
    // 节点不为空，让深度加一
    deep++
    // 更新最大深度
    result = Math.max(result, deep)
    travel(root.left, deep)
    travel(root.right, deep)
    // 遍历完毕返回上一层节点，深度减一
    deep--
  }
  travel(root, deep)
  return result
}

子树最大深度加一

解决子问题，之后+1就是答案

function maxDeep (root){
  if(root === null) return 0
  // 把左右节点作为子问题来处理
  const leftMax = maxDeep(root.left)
  const rightMax = maxDeep(root.right)
  // 当前节点的 + 左右节点深度的最大值
  return 1 + Math.max(leftMax, rightMax)
}