二叉树深度：最大与最小

计算二叉树的最大深度和最小深度

问题

给定一棵二叉树，分别求出它的最大深度和最小深度。

最大深度：根节点到最远叶子节点的路径长度
最小深度：根节点到最近叶子节点的路径长度

解答

二叉树节点定义

function TreeNode(val, left = null, right = null) {
  this.val = val;
  this.left = left;
  this.right = right;
}

最大深度

递归（DFS）

function maxDepth(root) {
  // 空节点深度为 0
  if (!root) return 0;
  
  // 取左右子树的最大深度 + 1
  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

迭代（BFS）

function maxDepth(root) {
  if (!root) return 0;
  
  const queue = [root];
  let depth = 0;
  
  while (queue.length) {
    const size = queue.length;
    depth++;
    
    // 处理当前层的所有节点
    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
  }
  
  return depth;
}

最小深度

递归（DFS）

function minDepth(root) {
  if (!root) return 0;
  
  // 左子树为空，只看右子树
  if (!root.left) return minDepth(root.right) + 1;
  
  // 右子树为空，只看左子树
  if (!root.right) return minDepth(root.left) + 1;
  
  // 都不为空，取较小值
  return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
}

迭代（BFS）

function minDepth(root) {
  if (!root) return 0;
  
  const queue = [root];
  let depth = 0;
  
  while (queue.length) {
    const size = queue.length;
    depth++;
    
    for (let i = 0; i < size; i++) {
      const node = queue.shift();
      
      // 遇到叶子节点，直接返回
      if (!node.left && !node.right) {
        return depth;
      }
      
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
  }
  
  return depth;
}

测试

//       1
//      / \
//     2   3
//    / \
//   4   5

const root = new TreeNode(1,
  new TreeNode(2, new TreeNode(4), new TreeNode(5)),
  new TreeNode(3)
);

console.log(maxDepth(root)); // 3
console.log(minDepth(root)); // 2

关键点

最小深度必须到叶子节点：如果一侧子树为空，不能算作深度 0，必须走另一侧
BFS 求最小深度更高效：遇到第一个叶子节点就能返回，不用遍历整棵树
递归的终止条件：空节点返回 0，这是递归的基础
层序遍历的技巧：用 size 记录当前层节点数，确保按层处理