面试题库 › C++ / 后端 › 二叉树最小深度的递归与迭代解法

二叉树最小深度的递归与迭代解法

难度 ★☆☆在 5 场真实面经中被问到 方向:C++ / 后端考点:树与二叉树

哪些公司问过

美团2腾讯1快手1腾讯音乐1

常见岗位:C/C++ 软件开发、Go 后端、Java 后端

答案要点

  1. 最小深度是根到最近叶子节点的路径节点数,叶子指左右孩子都为空的节点
  2. 递归:空树返回 0,叶子返回 1,两侧都不空取较小值加一
  3. 单侧子树为空时要返回非空一侧深度加一,不能直接取 min
  4. 迭代用 BFS 按层遍历,遇到第一个叶子即返回当前层数
  5. 时间复杂度均为 O(n),递归空间 O(h),BFS 空间为最宽层节点数

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题