zhangdizhangdi

104.二叉树的最大深度

题目

LeetCode 简单

给定一个二叉树 root ，返回其最大深度。
二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。

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

题解

方法：深度优先

DFS 递归 O(n) O(height)

ts
function maxDepth(root: TreeNode | null): number {
  let max = 0

  const dfs = (node: TreeNode, depth: number) => {
    console.log('node', node?.val, 'depth', depth)

    if (!node) return
    if (!node.left && !node.right) {
      max = Math.max(max, depth)
    }
    if (node.left) dfs(node.left, depth + 1)
    if (node.right) dfs(node.right, depth + 1)
  }

  dfs(root, 1)

  return max
}

const tree = new Tree([3, 9, 20, 8, null, 15, 7])
console.log('🌰', maxDepth(tree.root))

方法：广度优先【todo⌛️】