面试题库 › C++ / 后端 › 高度为h的二叉树最少有几个节点?n个节点高度范围是多少?

高度为h的二叉树最少有几个节点?n个节点高度范围是多少?

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

哪些公司问过

快手2华为1

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

答案要点

  1. 先明确高度定义:根算第 1 层还是第 0 层
  2. 高度为 h 的二叉树最少 h 个节点(链状),最多 2^h-1 个(满二叉树)
  3. n 个节点的最小高度为 ⌈log2(n+1)⌉,最大高度为 n
  4. 例:50 个节点最小高度 6,最大高度 50
  5. 完全二叉树最少 2^(h-1) 个节点;AVL 最少节点数 N(h)=N(h-1)+N(h-2)+1

易错点

面试官常见追问

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

相关面试题