104. 二叉树的最大深度 🟩

题目

LeetCode 简单

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

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

题解

方法：深度优先

DFS 递归

时间复杂度：O(n)
空间复杂度：O(height)

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))

方法：迭代

在 JS 中，既可以用栈（pop() 弹出尾部，做深度优先遍历 DFS），也可以用队列（shift() 弹出头部，做广度优先遍历 BFS）。两者逻辑在这道题里完全通用。

时间复杂度：O(n)
空间复杂度：O(n)

// 1. 定义二叉树节点
class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val
    this.left = left
    this.right = right
  }
}

function maxDepth(root) {
  if (root === null) return 0

  let max = 0
  // 栈里存放的是[当前节点, 当前节点的深度]
  const stack = [[root, 1]]

  while (stack.length > 0) {
    console.log(
      'stack',
      JSON.stringify(stack.map(([node, depth]) => [node.val, depth])),
    )

    // 弹出栈顶元素进行处理 (DFS)
    const [node, depth] = stack.pop()

    // 挑战并刷新全局最大深度
    max = Math.max(max, depth)

    // 如果有子节点，把子节点和“深度+1”绑定后压入栈中
    if (node.left) {
      stack.push([node.left, depth + 1])
    }
    if (node.right) {
      stack.push([node.right, depth + 1])
    }
  }

  return max
}

//       3
//      / \
//     9   20
//         / \
//        15  7
const treeA = new TreeNode(3)
treeA.left = new TreeNode(9)
treeA.right = new TreeNode(20, new TreeNode(15), new TreeNode(7))

console.log('🌰', JSON.stringify(maxDepth(treeA))) // 3

执行结果

stack [[3,1]]
stack [[9,2],[20,2]]
stack [[9,2],[15,3],[7,3]]
stack [[9,2],[15,3]]
stack [[9,2]]
🌰 3

本页目录