面试题库 › 客户端 › k 叉树的高度如何计算

k 叉树的高度如何计算

难度 ★☆☆在 1 场真实面经中被问到 方向:客户端考点:树与二叉树

哪些公司问过

腾讯1

常见岗位:iOS

答案要点

  1. 具体树:高度 = 1 + 所有孩子高度的最大值,空树为 0,O(n)
  2. 深树可改用层序遍历避免栈溢出
  3. 满 k 叉树 h 层节点数为 (k^h - 1)/(k - 1)
  4. n 个节点的完全 k 叉树高度为 ⌈log_k((k-1)n + 1)⌉
  5. 最小高度即完全 k 叉树高度,最大高度为 n

易错点

面试官常见追问

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

相关面试题