面试题库 › 客户端 › 分裂二叉树的最大乘积(LC1339)

分裂二叉树的最大乘积(LC1339)

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

哪些公司问过

网易互娱1

常见岗位:C++ / Qt 客户端

答案要点

  1. 删一条边后,一部分是某节点子树,乘积为 sub×(total−sub)
  2. 第一次遍历求总和 total
  3. 第二次后序遍历求每个子树和,同时更新最大乘积
  4. 乘积用 64 位整型,比较完最大值后再对 1e9+7 取模
  5. 时间 O(n),空间 O(h)

易错点

面试官常见追问

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

相关面试题