面试题库 › Java 后端 › 二叉树中不相邻节点和的最大值

二叉树中不相邻节点和的最大值

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

哪些公司问过

字节跳动1

常见岗位:C++ 后端

答案要点

  1. 每个节点维护两个状态:选当前节点、不选当前节点
  2. 选:自身值 + 左孩子不选 + 右孩子不选
  3. 不选:左孩子两状态较大者 + 右孩子两状态较大者
  4. 后序遍历,空节点返回 (0,0),答案为根的两状态较大者
  5. 时间 O(n),空间 O(h),避免对孙子节点重复递归

易错点

面试官常见追问

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

相关面试题